Bit Strings

Your task is to calculate the number of bit strings of length $nn$.

For example, if $n=3n=3$, the correct answer is $88$, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Input

The only input line has an integer $nn$.

Output

Print the result modulo ${10}^9+710^9+7$.