Skills101
← All coding problems

N-th Fibonacci Number (Huge N)

mediumPlacement Coding+20 XPTime limit 2s

The Fibonacci numbers are F(0) = 0, F(1) = 1 and F(n) = F(n − 1) + F(n − 2). For each n, print F(n) modulo 1,000,000,007.

Input:

  • line 1: q
  • next q lines: one integer n

Output: q lines — F(n) mod 1000000007.

Constraints: 1 ≤ q ≤ 1000, 0 ≤ n ≤ 10¹⁸.

Think about it: a loop up to 10¹⁸ never finishes. Use fast doubling: F(2k) = F(k)·(2·F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)². This halves n at each step — about 60 steps. (Matrix exponentiation of [[1,1],[1,0]] also works.)

Sample input 1

4
0
1
10
50

Sample output 1

0
1
55
586268941

Sample input 2

1
100

Sample output 2

687995182

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.