← 返回题目列表

AtCoder · KeioPC2025_f

F. 不喜欢 321

中文机器翻译题面 查看原题

配点 : 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