Taco Fibonacci

This problem requires you to calculate the n^th Fibonacci number using dynamic programming with a modulo operation. The Fibonacci sequence is defined as follows:

• F(1) = 0
• F(2) = 1
• For n ≥ 3, F(n) = F(n-1) + F(n-2)

Since the numbers can grow very large, you are required to compute the answer modulo \(10^9+7\). That is, you must output the value:

\(F(n) \bmod (10^9+7)\)

Note: The sequence is defined with 1-indexing, meaning the first Fibonacci number is 0.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10⁶), which represents the position in the Fibonacci sequence. The first number corresponds to 0 and the second to 1.

outputFormat

Output a single integer, the n^th Fibonacci number computed under modulo \(10^9+7\>.

1

0