Growth Function values <PB>

1

1 votes
Recruit, Approved, Ready, Easy, Grammar-Verified, Mathematics, Matrix Exponentiation
Problem

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(x1) + 2 * f(x2) + 3 * f(x3) + f(x4), 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 109+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 109+7.

Constraints

1T104
1N1018

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For value of n=2 you can clearly see that the value of function is also 2. Rest of the values can be simply calculated by entering the value of n in the function based on the recurrence relation

Editor Image

?