Balance (1) P92795

Given n weights 2⁰, 2¹, …, 2ⁿ⁻¹, 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 ≤ n ≤ 10⁶.

Output

For every case, print the number of correct ways modulo 10⁹ + 7.

Observation

This problem is basically problem 4 of IMO 2011.