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

hide comments
rangey_18o3_20: 2021-12-31 20:45:31

Can be done by matrix expo in O(10^3*log(n) )
Was a pain but still worked

may_007: 2019-06-16 21:09:07

AC in one go

aman_sachin200: 2018-06-14 15:17:57

Top Down Works!!:P

smso: 2018-06-08 11:25:25

dp + avoid unnecessary work e.g. solution to 25 contains that to 3

holmesherlock: 2018-01-26 19:43:21

simple dp

burninggoku: 2017-09-21 12:54:57

0(n) algo ... :)

dwij28: 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.

i_rule_here: 2016-08-19 20:07:03

are the numbers in password distinct???

RISHABH THUKRAL: 2016-07-31 22:44:07

can someone give some testcases

naruto09: 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..??


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