合并
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
黑板上有 n 个数，为了简化问题，他们依次为 1 . . . n。
每次你可以选择两个数，擦掉他们，假设选择的数为 i, j, 那么你需要重新将(i+j)/2写到黑板上。
重复以上操作 n − 1 次后，黑板上只会剩下一个数，你需要求出最后剩下的数的最大值。
假设最后剩下的数最大值为 b, 那么令 a = 2^(n−1)b, 可以证明 a 是一个整数。由于 a 可能很大，所以
你需要输出 a 对 10^9 + 7 取模的余数。
Input
一行一个整数 n。
Output
一行一个整数，表示 a 对 10^9 + 7 取模的余数。
Examples
输入样例1:
3
输出样例1:
9
Notes
对 20% 的数据，n ≤ 1000
对 40% 的数据，n ≤ 10^6
对 100% 的数据，n ≤ 10^9
