Riffle Swap

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem G: Riffle Swap

You have a deck of 2N cards (1 ≤ N ≤ 1000000) and want to have them shuffled.

The most popular shuffling technique is probably the riffle shuffle, in which you split a deck into two halves, place them in your left and right hands, and then interleave the cards alternatively from those hands. The shuffle is called perfect when the deck is divided exactly in half and the cards are interleaved one-by-one from the bottom half. For example, the perfect riffle shuffle of a deck of eight cards <0, 1, 2, 3, 4, 5, 6, 7> will result in a deck <0, 4, 1, 5, 2, 6, 3, 7>.

Since you are not so good at shuffling that you can perform the perfect riffle shuffle, you have decided to simulate the shuffle by swapping two cards as many times as needed. How many times you will have to perform swapping at least? As the resultant number will obviously become quite huge, your program should report the number modulo M = 1000003.

Input

The input just contains a single integer N.

Output

Print the number of swaps in a line. No extra space or empty line should occur.

Sample Input and Output

Input #1

1

Output #1

0

Input #2

2

Output #2

1

Input #3

3

Output #3

4

Input #4

4

Output #4

10

Input #5

10

Output #5

916

Source: ACM-ICPC Japan Alumni Group Winter Camp , Day 3, Tokyo, Japan, 2009-02-23
http://acm-icpc.aitea.net/