P2675 "Qu Pa's Number Game" T3 - Triangle Sanctuary

King 1 leads everyone to the center of the Kingdom of Numbers: the Triangle Sanctuary.

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: ```plain 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$.

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

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

- Sample Explanation One feasible arrangement is: ```plain 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