Problem L
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\le N\le 10000$) 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.

2

2

4

5