SAFECRAC - Crack the Safe

Johnny (not little anymore) is a super agent .He is been following up on leads against the world’s worst terrorists. He got a intel that a terrorist is staying at an expensive hotel. Only thing that stops LJ is the secure door in the room entrance.

The secure door had a lock which resembled this,

1 2 3
4 5 6
7 8 9
0 Enter

The enter key cannot be a part of the pass-code

When Johnny did some spy work on it, he found out that every pair of neighbouring digits in the pass code is adjacent on the keypad. Adjacent means that the digits share a common edge.

Now he wants to know how many different possibilities are there for the pass code so that he can bring a computer accordingly to hack the lock.

Input

Input begins with single integer ‘T’ denoting number of test cases and T lines follow. Each line contains the number ‘N’ denoting the length of the pass code.

Output

For each test case T, output the number of different possibilities in a new line. Since the answer can be huge output the number mod 1000000007.

Constraints:

1 <= T <= 1,000

1 <= N <= 100,000

Sample

Input: 
2
3
25

Output:
74
478325846

Added by:J.A.R.V.I.S.
Date:2013-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2021-12-31 20:45:31
Can be done by matrix expo in O(10^3*log(n) )
Was a pain but still worked
2019-06-16 21:09:07
AC in one go
2018-06-14 15:17:57
Top Down Works!!:P
2018-06-08 11:25:25
dp + avoid unnecessary work e.g. solution to 25 contains that to 3
2018-01-26 19:43:21
simple dp
2017-09-21 12:54:57 burninggoku
0(n) algo ... :)
2016-10-14 15:48:09
Ahh, my life revolves around corner cases. Got 1 WA because i did not precompute value for n = 1 (ans = 10). It's simple O(n) dp. Can't think of a logarithmic solution right now.
2016-08-19 20:07:03
are the numbers in password distinct???
2016-07-31 22:44:07 RISHABH THUKRAL
can someone give some testcases
2016-04-08 19:37:53
The code that gets accepted in C++4.3.2 gets wrong answer in C++14..Why is this so..??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.