Fibonacci Sequence

View as PDF
Submit solution
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}

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

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

Input Specification

The first line of input will have the number N.

Output Specification

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

Sample Input

26

Sample Output

121393

Comments


  • 29
    FatalEagle  commented on Sept. 16, 2014, 1:16 a.m. ← edit 2

    The problem requires you to output mod 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. This operation can be done in Python, C++, and Java by using %.

    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 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*}


  • 13
    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}.