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) \bmod 1\,000\,000\,007~ 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