crazy-numbers-1

Golu is crazy about numbers. He loves those numbers such that the difference between the adjacent digits of that number is exactly one. He calls these numbers crazy numbers and wants to find out how many such numbers exist for N number of digits. This task is very difficult for him so he wants your help.

Now your task is to find how many N digit crazy numbers exist such that the difference between the adjacent digits of the number is exactly one. 
For eg: For N = 3, crazy numbers are  123 , 434 , 567  etc. Numbers like 576, 453 etc. are not considered crazy numbers.    

Note: Number must not contain any leading zeroes.

Input: 
The first line contains the number of test cases T. 
Next T lines contains number of digits i.e. N.  

Output:
 Find out how many crazy numbers exist containing exactly N digits. Output can become large, so take modulo with 10^9+7 i.e. 1000000007.

Constraints:
1 ≤ T ≤100
1 ≤ N ≤10^6

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
10
17

Explanation

For N=1, crazy numbers are  0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 .

For N=2, crazy numbers are 10 , 12 , 21 , 23 , 32 , 34 , 43 , 45 , 54 , 56 , 65 , 67 , 76 , 78 , 87 , 89 , 98.

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming


Solutions: