Balance (1) P92795

Given $n$ weights $2^0$, $2^1$, …, $2^{n-1}$, we have to place all the weights on a balance, one after another, in such a way that the right pan is never heavier than the left pan. Please compute the number of ways of doing this.

For example, for $n = 2$ there are exactly three ways: placing first 2 on the left pan and then 1 on the right pan, placing first 2 on the left pan and then 1 on the left pan, and placing first 1 on the left pan and then 2 on the left pan. Note that, for instance, placing first 1 on the right pan and then 2 on the left pan is an incorrect way, since after placing 1 the right pan is heavier than the left pan.

Input

Input consists of several cases, each with a natural number $1 \le n \le 10^6$.

Output

For every case, print the number of correct ways modulo $10^9 + 7$.

Observation

This problem is basically problem 4 of IMO 2011.