Hide

# 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 |