AT_KeioPC2025_f (1,2,...,N) の順列のうち長さ 3 の単調減少な連続部分列を含まないものの個数 mod 10^9+9 を知りたい

求长度为 $N$ 的序列 $(1,2,\dots,N)$ 的所有排列中，不包含长度为 $3$ 的单调递减连续子序列的排列个数，并输出结果对 $10^9 + 9$ 取模后的值。

输入包含一行，包含一个整数 $N$。

输出一个整数，表示满足条件的排列个数对 $10^9 + 9$ 取模后的结果。

## 部分分 本题存在部分分。 - 对于满足 $N \le 3000$ 的数据集，答对可得 $1$ 分。 ## 样例解释 1 对于 $N=3$，$(1,2,3)$ 的所有排列中，除 $(3,2,1)$ 外有 $5$ 个满足条件。 ## 约束条件 - $1 \le N \le 1.7 \times 10^7$ - $N$ 为整数。 由 ChatGPT 5 翻译