Problem Description

Little Z has n small cubes placed side by side in his basement (Little Z is a passionate fan of Minecraft and loves decorating his basement with these cubes). Each cube is unique (Little Z likes things that are different from each other), such as grass blocks, marble, obsidian, etc.

Little Z likes to arrange these cubes in a special order, for example: grass block, marble, obsidian. One day, Little D helped Little Z organize the basement. However, the forgetful Little D moved all the cubes out and forgot their original positions. Relying on vague memories, he might have placed the cube that was originally at the i-th position into any of the (i-1), i, or (i+1) positions (of course, the first cube cannot be placed in the 0th position, and the n-th cube cannot be placed in the (n+1) position). For example (corresponding to the example above): marble, grass block, obsidian.

Little Z is a broad-minded person. He wants to calculate how many possible arrangements Little D could have made and does not hold Little D accountable (holding him accountable would only make things worse...). Since his own intelligence is also limited, if the answer is very large, he only wants to see the last 8 digits (leading zeros need not be shown to him).

Input Format

A single line containing a positive integer n, representing the total number of cubes in Little Z's basement.

Output Format

A single line containing a positive integer, representing the number of possible arrangements Little D could have made, showing only the last 8 digits, without leading zeros.

Sample Input and Output

Sample Input #1

3

Sample Output #1

3

Sample Input #2

987

Sample Output #2

223731

Notes

Sample Explanation 1

Following the example in the problem, there are 3 possible arrangements: (grass block, marble, obsidian), (marble, grass block, obsidian), (grass block, obsidian, marble).

Sample Explanation 2

There are... 00223731 possible arrangements. Since leading zeros are not output, the result is 223731.

Data Scale

There are 50 test cases.

• For the 1st to 15th cases: 1 < n <= 10^6
• For the 16th to 25th cases: 10^6 < n <= 10^16
• For the 26th to 50th cases: 10^16 < n <= 10^1000

Time and Space Limits

0.2s/64MB

见题面 Input 部分

见题面 Output 部分