配点 : 101 点
問題文
(1,2,\dots,N) 的排列中,长度 3 单调递减的连续子序列的数量为 除以 10^9 + 9 后求余数。
制約
- 1 \le N \le 1.7 \times 10^7
- N 是一个整数
部分点
针对此问题设置了部分分数。
- N \le 3000 的数据集 1 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N
出力
打印答案。 来自
入力例 1
3
出力例 1
5
(1,2,3) 的排列中,(3,2,1) 之外 5 满足条件。
入力例 2
6
出力例 2
349
入力例 3
123
出力例 3
756051385
入力例 4
17000000
出力例 4
430982110