J. Bubble Cup hypothesistime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe Bubble Cup hypothesis stood unsolved for 130 years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:Given a number m, how many polynomials P with coefficients in set {\{0,1,2,3,4,5,6,7\}} have: P(2)=m?Help Jerry Mao solve the long standing problem!InputThe first line contains a single integer t (1 \leq t \leq 5\cdot 10^5) - number of test cases.On next line there are t numbers, m_i (1 \leq m_i \leq 10^{18}) - meaning that in case i you should solve for number m_i.OutputFor each test case i, print the answer on separate lines: number of polynomials P as described in statement such that P(2)=m_i, modulo 10^9 + 7.ExampleInput
2
2 4
Output
2
4
NoteIn first case, for m=2, polynomials that satisfy the constraint are x and 2.In second case, for m=4, polynomials that satisfy the constraint are x^2, x + 2, 2x and 4.
2
2 4

2 4 
['bitmasks', 'constructive algorithms', 'dp', 'math', '*2400']