Climbing the Staircase

Difficulty: 1100 3000 ms 128 MB

dp

You climb a staircase of N steps taking 1 or 2 steps at a time. How many distinct step sequences reach the top, modulo 10⁹+7?

Input: one integer N.

Output: the number of ways mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 10⁶

Sample Tests

4

5

1

1

Read the Editorial