Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mystery of Fibonacci

By TarifEzaz, backbencher16 · Limits 1s, 512 MB

Fibonacci sequence is a recursive sequence that depends on the following definition:

Fib(N) = Fib(N-1) + Fib(N-2)
Fib(0) = 0 
Fib(1) = 1

In this problem you have to calculate this simple function. Given N, you have to calculate Fib(N) modulo 1000000007.

Input

Input contains a single line, N (1 ≤ N ≤ 109 ).

Output

You have to print one line with the value of Fib(N) modulo 1000000007.

Sample

InputOutput
2
1

Discussion

Statistics


43% Solution Ratio

SAIF_IITEarliest, 8M ago

SAIF_IITFastest, 0.0s

SAIF_IITLightest, 0 B

nightwielderShortest, 224B

Submit

Login to submit