GSWORDS - Counting Words

no tags 

Supervin likes counting. In this problem, he invites you to count together

Supervin defines a word as "a string only consist of 'o' or 'x'", and additional requirement, for each substring with prime-length, the number of 'o' is not less than the number of 'x'.

Supervin gives you an integer N (1 <= N <= 10^12). Supervin challenges you to determine how many words can be made with exactly N-length.

You are having difficulties, make a program to determine how many N-length words. Because the output can be too big, output the number of words modulo 1 000 000 007

Input

One line, an integer N

Output

One line, an integer indicates how many N-length words modulo 1 000 000 007

Example

Input:
2

Output:
3
Input:
3
Output:
4
Explanation :
In the first sample, the words can be made are : "oo", "ox", "xo".
In the second sample, the words can be made are : "ooo", "oox", "oxo", "xoo"

hide comments
rashigupta16: 2017-02-03 21:39:13

Great problem :)

mukesh227: 2015-10-30 21:25:08

finally AC!!!Hurrry!!!!

:.Mohib.:: 2015-01-16 11:15:17

Can anybody plzz provide some testcases???

re(vamsi): use brute force

Last edit: 2015-01-17 10:26:48
(Tjandra Satria Gunawan)(曾毅昆): 2012-08-06 10:26:59

@Jonathan Irvin Gunawan: Good luck, IOI 2012 at Sirmione, Italia. I know you're great programmer ;) hope you win the gold medal. "Lakukan yang terbaik untuk Indonesia" :D

(Tjandra Satria Gunawan)(曾毅昆): 2012-08-06 10:26:59

@Jonathan Irvin Gunawan: I agree with Mitch Schwartz, upload multiple test cases on single file allow you to add thousand of test cases and make the judge faster. Btw, Nice problem "Problem yang keren". Google +1 for your problem ;)

Mitch Schwartz: 2012-08-06 10:26:59

It seems better to me to have many test cases per input file (and maybe 1-4 input files), rather than ~50 separate input files each with just one test case. This is not only logistically easier but also easier on SPOJ servers. For example, if somebody tries an algorithm that will get TLE, right now it would use ~50 seconds of server time, because the way the judge works is to run the program against EVERY input file and only afterward report according to success or the first failure. Additionally, a Java submission would use close to 0.3 seconds for each test case just to start up the virtual machine. Also it makes users wait a little longer to see the result of their submission, although this is a smaller concern.


Added by:jonathanirvings
Date:2012-08-06
Time limit:0.813s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Jonathan Irvin Gunawan, used in TOKI OpenContest March 2012