题目描述

黑板上有 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