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{align*} X &= (F(n-1))^2 \bmod 1\,000\,000\,007 \\ Y &= X \times \lfloor \log_2 X \rfloor \\ F(n) &= Y \times (Y + F(n-1))^2 \end{align*}$$

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