Background

King 1 leads everyone to the heart of the Digital Kingdom: the Triangle Sanctuary.

Problem Description

Isn't the triangle the most stable shape? The heart of the Digital Kingdom is formed by an inverted triangle. At the top of this inverted triangle is a row of numbers, ranging from 1 to N. The positions of these numbers from 1 to N can be swapped. Each subsequent row of numbers is derived by adding the two adjacent numbers from the previous row. Consequently, the bottom-most number becomes quite large! The Digital Kingdom refers to this number as the "Foundation." King 1 desires the Foundation to be as large as possible, but performing the addition himself is too tedious. He hopes you can help him calculate the maximum value of this number through programming, and since this value might be very large, please output the result modulo 10007.

Task: Given N, find the maximum Foundation of the triangle formed by numbers 1 to N, then output it modulo 10007.

Input Format

A single integer N.

Output Format

A single integer, representing the maximum Foundation of the triangle formed by numbers 1 to N.

Sample Input and Output

Sample Input #1

4

Sample Output #1

24

Sample Input #2

1125

Sample Output #2

700

Notes

Data:

• 20% of cases: 0 <= N <= 100
• 50% of cases: 0 <= N <= 3000
• 100% of cases: 0 <= N <= 1000000

Sample Explanation:

For N = 4, the maximum value is 24, achieved by the arrangement:

1   3   4   2
4   7   6
11  13
24

There are other possible arrangements as well.

PS: It's called the Triangle Sanctuary, but it's really just a triangle.

The data for this problem has been updated and is now completely correct!

Do not program specifically for the data!

见题面 Input 部分

见题面 Output 部分