Fibonacci numbers (1) P72994


Statement
 

pdf   zip

html

The Fibonacci numbers Fn are defined as follows:

Fn = 



0if n = 0 
1if n = 1 
Fn−1 + Fn−2if n ≥ 2

Therefore, the first Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

For every given natural number n, compute Fn mod108 + 7.

Input

Input consists of several n. Assume 0 ≤ n ≤ 105.

Output

For every given n, print Fn mod108 + 7.

Public test cases
  • Input

    0
    1
    10
    100000
    

    Output

    0
    1
    55
    33178829
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++ Haskell