Mystery of Fibonacci

TarifEzaz, backbencher16 SCB-PA Inter School and C...
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

Submit

Login to submit.

Statistics

42% Solution Ratio
SAIF_IITEarliest, Sep '19
SAIF_IITFastest, 0.0s
SAIF_IITLightest, 0 B
nightwielderShortest, 224B
Toph uses cookies. By continuing you agree to our Cookie Policy.