This problem requires to compute some numbers!

Input Specification

First line: $N$, number of iterations

Second line: 16 numbers, each of them $\le 2^{32}-1$

Output Specification

For each number, let it be $F(0)$.

Do these computations in order:

$${\displaystyle \begin{array}{rl}X& =(F(n-1){)}^{2}mod1000000007\\ Y& =X\times \lfloor {\log }_{2}X\rfloor \\ F(n)& =Y\times (Y+F(n-1){)}^2\end{array}}$$

Also, if $X=0$ then $Y=0$. For each number, output sum of $F(i)mod1000000007$ for each $i$ from $0$ to $N-1$.

Constraints

Subtask 1 [100%]

$N={10}^8$

Subtask 2 [0%]

Sample test cases.

Sample Input

10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output

1 4732602024 6148672003 4338052043 4483023256 4518465763 4649308948 3879800457 3164030163 3788568405 6057821801 5081899390 3575845616 4623378973 4148490590 5052851606