AKVDDN03 - Butters solves Recurrences 450 pts
Butters likes to solve Recurrence Relations. He wants to solve them really fast. He got this relation:
F(n) = 2 * F(n - 1) + 3 * F(n - 2), with F(1) = 1 and F(2) = 2
So the series becomes:
1 2 7 20 61 ...
So the first term is 1, 2nd term is 2, 3rd term in 7 and so on. He wants to know the Nth term of this series. Since the answer can be really large, he wants to find it modulo 1000000007.
Input
First line will contain "T" the number of test cases. Each of the next "T" lines will contain an integer N, the term which Butters wants to find.
Output
For each test case print the Nth term of this series modulo 1000000007.
Constraints
1 <= T <= 10^5
1 <= N <= 10^9
Example
Input: 5 1 5 10 2 1000 Output: 1 61 14762 2 14222048
Added by: | Ankit Kumar Vats |
Date: | 2013-08-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Self |