Latin Stones
总提交:539 测试通过:75
描述
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.
输入
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.
输出
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.
样例输入
2
样例输出
21
题目来源
NUAA
