Description

The center of the Kingdom of Numbers is formed by an inverted triangle.

The inverted triangle has $N$ layers. The $i$-th layer from top to bottom contains $N - i + 1$ numbers. The first layer must be one of the permutations of $1 \sim N$, that is, it must use all numbers from $1$ to $N$ without repetition. Starting from the second layer, each number is obtained by adding the two numbers above it to the left and right. For example, the following is a valid inverted triangle:

1   2   3   4
  3   5   7
    8   12
      20

This inverted triangle has $N = 4$, and the last-layer number is $20$.

The Kingdom of Numbers calls the last-layer number the 'base'. Please write a program to compute the maximum value of the 'base' modulo $10007$.

Input Format

One line containing an integer $N$, representing the number of layers of the inverted triangle.

Output Format

One line containing an integer, which is the maximum possible 'base' for $N$ layers modulo $10007$.

4

24

1125

700

Hint

• Sample Explanation

One feasible arrangement is:

1   3   4   2
  4   7   6
    11  13
      24

It can be proved that there is no better method.

• Constraints

For $20\%$ of the testdata, $N \le 100$.

For $50\%$ of the testdata, $N \le 3000$.

For $100\%$ of the testdata, $0 \le N \le {10}^6$.

Translated by ChatGPT 5