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

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 3.5medium
Statistics Show