Trains X69569

Michelangelo has attended the 75 AD gladiator fights at the Colosseum and now wants to travel back to his own time in 1505 AD. He decides to take the time train at the Termini station.

Instead of stopping at different stations, the time train stops at the same station, but at different times. Specifically, the regular time train stops every minute at the Termini station. Every minute there are also express trains that only stop every three minutes.

Since Michelangelo has been taking math lessons by his good friend Leonardo, he starts thinking about the number of different ways in which he can travel home. For example, if he has to travel a total of 5 minutes, there are 4 ways of going home:

• Take the regular time train for 5 minutes.
• Take the express train for 3 minutes, then the regular train for 2 minutes.
• Take the regular train for 1 minute, then the express train, then the regular train.
• Take the regular train for 2 minutes, then the express train.

Input

The input consists of several test cases. Each test case consists of a number of minutes n such that 1≤ n≤ 1000000000000.

Output

For each test case, compute the number of ways in which Michelangelo can travel home. Since this number can be very large, output the number modulo 1000003.