問題文

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

制約

• 1 \le N \le 1.7 \times 10^7
• N は整数

部分点

この問題には部分点が設定されている。

• N \le 3000 を満たすデータセットに正解した場合 1 点が与えられる。

入力例 1

3

出力例 1

5

(1,2,3) の順列のうち、(3,2,1) 以外の 5 個が条件を満たします。

入力例 2

6

出力例 2

349

入力例 3

123

出力例 3

756051385

入力例 4

17000000

出力例 4

430982110