Hide

Problem D
Snakes and Masters

You and your friends are playing a game of Snakes and Masters. The goal of the game is to land in a specific square to win the game. From where you are, it requires $N$ steps to land on the specific square. Each turn you are allowed to take either one or two steps. How many distinct ways can you reach the winning square?

Input

The input consists of a single integer $N$ ($1 \leq N \leq 10\, 000$) representing the number of steps you are away from the winning square.

Output

Output mod $10^6$ of the number of distinct ways you can reach the winning square.

Sample Input 1 Sample Output 1
2
2
Sample Input 2 Sample Output 2
4
5

Please log in to submit a solution to this problem

Log in