---

Problem 720

---

Unpredictable Permutations

Consider all permutations of ${1, 2, \ldots N}$, listed in lexicographic order.
For example, for $N=4$, the list starts as follows:

$$\displaylines{
(1, 2, 3, 4) \
(1, 2, 4, 3) \
(1, 3, 2, 4) \
(1, 3, 4, 2) \
(1, 4, 2, 3) \
(1, 4, 3, 2) \
(2, 1, 3, 4) \
\vdots
}$$

Let us call a permutation $P$ unpredictable if there is no choice of three indices $i \lt j \lt k$ such that $P(i)$, $P(j)$ and $P(k)$ constitute an arithmetic progression.
For example, $P=(3, 4, 2, 1)$ is not unpredictable because $P(1), P(3), P(4)$ is an arithmetic progression.

Let $S(N)$ be the position within the list of the first unpredictable permutation.

For example, given $N = 4$, the first unpredictable permutation is $(1, 3, 2, 4)$ so $S(4) = 3$.
You are also given that $S(8) = 2295$ and $S(32) \equiv 641839205 \pmod{1\ 000\ 000\ 007}$.

Find $S(2^{25})$. Give your answer modulo $1\ 000\ 000\ 007$.

---

不可预测的排列

考虑集合${1, 2, \ldots N}$的所有排列，并按字典序组成列表。
例如，对于$N=4$，所有排列组成的列表如下所示：

$$\displaylines{
(1, 2, 3, 4) \
(1, 2, 4, 3) \
(1, 3, 2, 4) \
(1, 3, 4, 2) \
(1, 4, 2, 3) \
(1, 4, 3, 2) \
(2, 1, 3, 4) \
\vdots
}$$

对于排列$P$，如果不存在三个下标$i \lt j \lt k$使得$P(i), P(j), P(k)$构成等差数列，则称该排列为不可预测的。
例如，$P=(3, 4, 2, 1)$不是不可预测的，因为$P(1), P(3), P(4)$构成等差数列。

记$S(N)$为在上述列表中第一个不可预测排列的位置。

例如，对于$N = 4$，第一个不可预测排列是$(1, 3, 2, 4)$，因此$S(4) = 3$。
已知$S(8) = 2295$，$S(32) \equiv 641839205 \pmod{1\ 000\ 000\ 007}$。

求$S(2^{25})$，并将你的答案对$1\ 000\ 000\ 007$取余。

---