Vivid is good at higher mathematics. So his classmates call him the little prince of higher mathematics. However, during the final exam of higher mathematics, he was got stuck with the last problem. So he may turn to you for help, if you do a good job you may get a generous remuneration.
Here is the statement of that problem.
Here is a differential equation about f(x), $\left\{\begin{matrix}{f{\left( x \right)}}^{"}=f{\left( x \right)}\\ {f{\left( 0 \right)}=f{\left( 0 \right)}}^{'}=1\end{matrix}\right.$
, and $g\left( x \right) = \frac{x}{{f\left( x \right) - 1}}$ , you are expected to calculate $\mathop {\lim }\limits_{x \to 0} {\kern 1pt} {\kern 1pt} {\kern 1pt} g{\left( x \right)^{\left( n \right)}}$ .$g{\left( x \right)^{\left( n \right)}}$ is the N derivative of $g\left( x \right)$ , i.e. $\left\{ \begin{array}{l}
g{\left( x \right)^{\left( 0 \right)}} = g\left( x \right)\\
g{\left( x \right)^{\left( n \right)}} = {\left[ {g{{\left( x \right)}^{\left( {n - 1} \right)}}} \right]^\prime }{\kern 1pt} {\kern 1pt} {\kern 1pt} for{\kern 1pt} {\kern 1pt} {\kern 1pt} n{\kern 1pt} {\kern 1pt} \ge 1
\end{array} \right.$ .
The result may be a fraction, but Vivid loves integer very much. So he designs a function ftoi(x) to turn a fraction into an integer.
ftoi(x)
{
MOD=1000000007;
sign=1;
if(x<0)
{
x=-x;
sign=-1;
}
if(x is not simplest fraction)set x to the simplest fraction which equals to x;
up=numerator of x;
down=denominator of x;
inv is the minimun non-negative integer which makes inv*down%MOD=1 hold;
(sometimes inv may not exist, but in this problem you can assume that there is no such case.)
return (inv*up*sign%MOD+MOD)%MOD;
}
For example ftoi(1)=1, ftoi(-1)= 1000000006, ftoi(-2/4)=ftoi(-1/2)= 500000003, ftoi(6/12)=ftoi(1/2)= 500000004
Input
Multi test cases (about 60000), each case will give n in a single line.
Process to the end of file.
[Technical Specification]
0<=n<65536
Output
For each n, output $ftoi{\left( \mathop {\lim }\limits_{x \to 0} {\kern 1pt} {\kern 1pt} {\kern 1pt} g{\left( x \right)^{\left( n \right)}} \right)}$ in a single line.
