- Time limit: 1.00 s
- Memory limit: 512 MB
For example, if $n=3$, the correct answer is $8$, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.
Input
The only input line has an integer $n$.
Output
Print the result modulo $10^9+7$.
Constraints
- $1 \le n \le 10^6$
Input:
3
Output:
8