Nth fibonacci number

Fibonacci Series is defined by the recurrence

    F(n) = F(n-1) + F(n-2), 

where F(n) is the Nth term of Fibonacci Series and F(1) = F(2) = 1. Provided N you have to output the Nth Fibonacci Number mod 1000000007 (10^9 + 7).

Input Format:

Line 1 : N (1 <= N <= 10^15)

Output Format:

You have to return Nth Fibonacci number mod 1000000007 (10^9 + 7)

Sample Input:
3
Sample Output:
2

Login to submit your solution

Fb dab53a1a64929320dc7425896aa73fd9e5512b6ab52e414ff5f3ebb5cecc73eb

Share Problem