CSES - Fibonacci Numbers

View as PDF
All submissions
Best submissions
Authors:
kitsune , Elektrikar
Problem types
Points: 1500 Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

The Fibonacci numbers can be defined as follows:

  • \(F_0=0\)
  • \(F_1=1\)
  • \(F_n=F_{n−2}+F_{n−1}\)

Your task is to calculate the value of \(F_n\) for a given \(n\).

Input

  • The only input line has an integer \(n\).

Output

  • Print the value of \(F_n\) modulo \(10^9+7\).

Constraints

  • $0\leq n\leq 10^{18} $

Example

Sample input

10

Sample output

55

Comments