Description

Ray is very excited today because Jiejie has finally agreed to give Ray some precious Latin Stones. The stones are all the same except for their colors. Every single stone has only one color and there are seven colors in all (Rumba, Samba, ChaChaCha, Jive, Paso Doble, Waltz, and FoxStep). Since these stones are very precious, Jiejie would like Ray to keep them in an elegant way that obeys the following rules: 1. Stones must be placed in a circle and the length of the circle is n. 2. Adjacent stones cannot have the same color. This problem really puzzles Ray and he even doubts whether there is a feasible way. So he asks you for help. Given the length of the circle, you should calculate how many different ways the stones can be arranged (ways that can be obtained by rotations should be counted as one). Assume the number of stones of each color is sufficient.

Input

There are multiple test cases. For each test case there is only one line that contains an integer n (less than 100,000) indicating the length of the circle.

Output

For each test case output one integer: the number of ways. Since this number can be really large, just output the reminder after being divided by 2003.

Sample Input

2

Sample Output

21

Source

NUAA