Fibonacci Sequence

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

The Fibonacci sequence is a well known sequence of numbers in which

$\displaystyle F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-2) + F(n-1), & \text{if } n \ge 2 \end{cases}$ $F (n) = {\begin{cases} 0, & if n = 0 \\ 1, & if n = 1 \\ F (n - 2) + F (n - 1), & if n \geq 2 \end{cases}$

Given a number $N$ $N$ $(1 \le N \le 10^{19})$ $(1 \leq N \leq 10^{19})$ , find the $N^{th}$ $N^{t h}$ Fibonacci number, modulo $1\,000\,000\,007$ $1 000 000 007$ $(= 10^9 + 7)$ $(= 10^{9} + 7)$ .

Note: For 30% of the marks of this problem, it is guaranteed that $(1 \le N \le 1\,000\,000)$ $(1 \leq N \leq 1 000 000)$ .

Input Specification

The first line of input will have the number $N$ $N$ .

Output Specification

The $N^{th}$ $N^{t h}$ Fibonacci number, modulo $1\,000\,000\,007$ $1 000 000 007$ $(= 10^9 + 7)$ $(= 10^{9} + 7)$ .

Sample Input

Copy

Sample Output

Copy

Comments

0

_va commented on March 31, 2024, 4:48 a.m.

it's harder than i imgine. i just AC 1 test.

47
FatalEagle commented on Sept. 16, 2014, 1:16 a.m. ← edit 2 →
The problem requires you to output mod $1\,000\,000\,007$ $1 000 000 007$ . That means that you need to get the remainder of the final answer when it is divided by $1\,000\,000\,007$ $1 000 000 007$ . This operation can be done in Python, C++, and Java by using %.

Copy
Example: 999999999999999999999999 mod 1000000007 is 999999999999999999999999 % 1000000007 which is equal to 48999999. Because 999999999999999999999999 = 999999993000000 * 1000000007 + 48999999, 48999999 is 999999999999999999999999 (mod 1000000007).

It may interest you to know that $1\,000\,000\,007$ $1 000 000 007$ is a prime number.

There are two highly useful properties of modular arithmetic we often use in programming competitions (% has the same precedence as multiplication and division):

$\displaystyle \begin{align*} (a + b) \bmod m &\equiv ((a \bmod m) + (b \bmod m)) \bmod m \\ (a \times b) \bmod m &\equiv ((a \bmod m) \times (b \bmod m)) \bmod m \end{align*}$ $\begin{aligned} (a + b) mod m & \equiv ((a mod m) + (b mod m)) mod m \\ (a \times b) mod m & \equiv ((a mod m) \times (b mod m)) mod m \end{aligned}$

26

quantum commented on Sept. 13, 2014, 8:30 p.m. ← edited →

This problem is a lot more difficult than it may appear. There is a reason for 15 points. The input can be as big as $10^{19}$ $10^{19}$ .