ITRIX12E - R Numbers


R - Numbers

R-numbers are numbers which have the property that they do not have the digit '0' and sum of every two adjacent digits of the number is prime. 123 is a R-number because 1+2 =3 and 2+3 =5 and 3, 5 are primes.

How many R-numbers can be formed with at most length N?

i.e. R-numbers of length 1 + R-numbers of length 2 + R-numbers of length 3 + ... R-numbers of length N.

Length of a number = Number of digits in the number.

Only four single digit numbers are R-numbers which are nothing but single digit primes 2, 3, 5, 7.

Input Specification

The first line of the input file contains T which denotes the number of test cases. The next T lines contain an integer N <= 10^9.

Output Specification

Print the numbers of R-numbers modulo 1000000007. [10^9+7];

Example

Sample Input:
2
1
2

Sample Output:
4
33

hide comments
Aman Kumar: 2012-04-10 22:12:14

@Tjandra...No..
for N=10^9 answer is..
757510247

uzumaki_naruto: 2012-04-10 21:11:46

how can length of a no be 10^9??

(Tjandra Satria Gunawan)(曾毅昆): 2012-04-10 04:52:49

Is the answer for N=10^9 is 498296368??


Added by:Radhakrishnan Venkataramani
Date:2012-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem