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 atmost 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
harshit2202: 2019-03-16 08:41:34

I can find it for particular N in log N
How to find it for atmost N because is N is too large

shahianshu: 2018-10-07 09:41:51

Amazing problem , solved using linear recurrence relation :)

masterchef2209: 2018-09-08 14:40:48

ONE HELL OF A QUESTION

arnauddesombre: 2018-08-23 17:36:48

(correct) answers for a few values of n:
1: 4
2: 33
3: 130
4: 454
5: 1545
10: 663370
100: 26514125
1000: 906016252
10000: 396515823
100000: 827019605
1000000: 294370820
10000000: 29572369
100000000: 530109085
1000000000: 757510247

narutorocks: 2016-06-03 09:16:25

NICE QUESTION LEARNT A LOT

harkirat: 2016-05-15 08:59:27

@david : wrong

David: 2013-09-24 20:17:39

Are the answers for 3, 4, and 5:
149
990
4354

(Tjandra Satria Gunawan)(曾毅昆): 2012-04-17 14:42:15

Finally I got AC...
@Aman Kumar: Thanks ;)

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??


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