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