The 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!
Output
For 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\).
Note
In 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 4
|
2
4
|