Maximizing the Base of the Inverted Triangle

The Digital Kingdom is centered around an inverted triangle built from numbers. The triangle has \(N\) rows. The first row (the top) consists of a permutation of \(1, 2, \dots, N\) (each number appears exactly once). From the second row onward, each number is the sum of the two numbers immediately above it (the left and right neighbors in the previous row). For example, the following is a valid triangle for \(N = 4\):

1   2   3   4
  3   5   7
    8   12
      20

The number at the bottom row is called the base (\(\text{基}\)). Your task is to rearrange the numbers of the first row (i.e. choose the permutation) so that the base value is maximized. Output the maximum possible base value modulo \(10007\).

Hint: If we denote the numbers in the first row as \(a_1, a_2, \dots, a_N\), then the base value can be expressed as

[ S = \sum_{j=1}^{N} \binom{N-1}{j-1} a_j. ]

Since the \(\binom{N-1}{j-1}\) coefficients (derived from Pascal's triangle) form a unimodal sequence, to maximize \(S\) we assign the largest number in the permutation to the position with the largest coefficient, the second largest to the second largest, and so on.

inputFormat

The input contains a single integer \(N\) (\(1 \leq N \leq \text{reasonable limit}\)) representing the number of rows of the inverted triangle.

outputFormat

Output a single integer, the maximum possible base value modulo \(10007\).

sample

4

24