Login
—
Dark mode
CSES Problem Set
Fibonacci Numbers
Task
Statistics
CSES - Fibonacci Numbers
Time limit:
1.00 s
Memory limit:
512 MB
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 \le n \le 10^{18}$
Example
Input:
10
Output:
55
Mathematics
...
Bracket Sequences II
Counting Necklaces
Counting Grids
Fibonacci Numbers
Throwing Dice
Graph Paths I
Graph Paths II
Dice Probability
...