ITRIX12E  R Numbers
R  Numbers
Rnumbers 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 Rnumber because 1+2 =3 and 2+3 =5 and 3 , 5 are primes.
How many Rnumbers can be formed with atmost length N?
i.e Rnumbers of length 1 + Rnumbers of length 2 + Rnumbers of length 3+....... Rnumbers of length N
Length of a number = Number of digits in the number
Only four single digit numbers are Rnumbers 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 Rnumbers modulo 1000000007. [10^9+7];
Example
Sample Input: 2 1 2 Sample Output: 4 33
hide comments
smso:
20210720 13:30:31
Used G.P. sum with common ratio in the form of matrix. 

harshit2202:
20190316 08:41:34
I can find it for particular N in log N


shahianshu:
20181007 09:41:51
Amazing problem , solved using linear recurrence relation :) 

masterchef2209:
20180908 14:40:48
ONE HELL OF A QUESTION 

arnauddesombre:
20180823 17:36:48
(correct) answers for a few values of n:


narutorocks:
20160603 09:16:25
NICE QUESTION LEARNT A LOT 

harkirat:
20160515 08:59:27
@david : wrong 

David:
20130924 20:17:39
Sorry  my bad and WA at the time.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120417 14:42:15
Finally I got AC...


Aman Kumar:
20120410 22:12:14
@Tjandra...No..

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