Hide
Problem G
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 |
