A new business growth estimate function named \(f(x)\) is out in the market which depends on a particular strategy and counts the total revenue that can be generated over x number of years. The function is defined as:

\(f (x)\) = 1, when x = 1
\(f (x)\) = 2, when x = 2
\(f (x)\) = 5, when x = 3
\(f (x)\) = 12, when x = 4
\(f (x)\) = \(f (x-1)\) + 2 * \(f (x-2)\) + 3 * \(f (x - 3 )\) + \(f (x - 4 )\), when x > 4

Ryan is working for the company Pitney Bowes and he is assigned the task to calculate the value of this function so that PB can estimate the profit. Since the function is too complex and he does not wants to defame his image so he asks you for the help. Now you are given an integer N by Ryan and you have to find the value of \(f(N)\) based on the conditions above.
Since the output can be large, print the answer Modulo \( 10^9+7 \).

Input format

• First line: T (number of test cases)
  For each test case
• First line: N

Output format

For each test case, print the value of \(f(N)\) Modulo \( 10^9+7 \).

Constraints

\(1 \le T \le 10^{4}\)
\(1 \le N \le 10^{18}\)