Matrix Exponentiation |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

The problem statement has recently been changed. View the changes.

×
C. Fibonacci

time limit per test

0.25 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFind the $$$n$$$-th Fibonacci number modulo $$$10^9+7$$$.

So, you need to find $$$F_n$$$ in the sequence defined as $$$F_0 = 0$$$, $$$F_1 = 1$$$ and $$$F_i = F_{i-1} + F_{i-2}$$$ for $$$i \geq 2$$$.

Input

An integer $$$n$$$ ($$$0 \leq n \leq 10^{18}$$$).

Output

Print the answer modulo $$$1000000007$$$.

Examples

Input

3

Output

2

Input

6

Output

8

Input

50

Output

586268941

Note

The first few terms of Fibonacci sequence are $$$(0, 1, 1, 2, 3, 5, 8, 13, \ldots)$$$. In particular, we have $$$F_0 = 0$$$, $$$F_3 = 2$$$ and $$$F_6 = 8$$$. And for the last sample test:

$$$$$$F_{50} = 12586269025 \equiv 586268941 \pmod {10^9 + 7}$$$$$$

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2024 14:25:30 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|