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

$ (1,2,\dots,N) $ の順列のうち、長さ $ 3 $ の単調減少な連続部分列を含まないものの個数を $ 10^9 + 9 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - $ N \le 3000 $ を満たすデータセットに正解した場合 $ 1 $ 点が与えられる。 ### Sample Explanation 1 $ (1,2,3) $ の順列のうち、 $ (3,2,1) $ 以外の $ 5 $ 個が条件を満たします。 ### Constraints - $ 1 \le N \le 1.7 \times 10^7 $ - $ N $ は整数