AT_s8pc_4_e.Enormous Atcoder Railroad

给你 $K$ 个车站，编号为 $S_0, S_1, \dots, S_{K-1}$，其中 $S_0=0$，$S_{K-1}=N$，且 $S_0 < S_1 < \dots < S_{K-1}$，各车站之间的距离满足 $1 \leq S_{i+1} - S_i \leq 10000$。 你可以选择恰好 $X$ 个中间车站（不能选择 $S_0$ 和 $S_{K-1}$），组成一条路径，要求路径是严格递增的序列，并且一定要包含起点 $S_0$ 和终点 $S_{K-1}$。求有多少种选择方式，使得路径合法。将答案对 $10^9+7$ 取模，并输出。

$N\ K\ X\ S_0\ S_1\ S_2\ ...\ S_{K-1}$

请输出一种合法路径的数量，对 $10^9+7$ 取模。
最后请换行。

约束条件

• $2 \leq K \leq 2500$。
• $1 \leq X \leq 2500$。
• $S_0 = 0, S_{K-1} = N$。
• $1 \leq S_{i+1} - S_i \leq 10000$。

得分规则

• 小子任务1 [$120$ 分]

  • $N, K, X \leq 15$。

• 小子任务2 [$90$ 分]

  • $K, X \leq 15$。
  • $S_{i+1} - S_i \leq 15$。

• 小子任务3 [$260$ 分]

  • $K, X \leq 40$。
  • $S_{i+1} - S_i \leq 40$。

• 小子任务4 [$160$ 分]

  • $K, X \leq 300$。
  • $S_{i+1} - S_i \leq 300$。

• 小子任务5 [$370$ 分]

  • 无额外约束。

样例解释 1

无法到达终点的站点集合有：$[0, 7], [0, 1, 7], [0, 1, 2, 7], [0, 1, 6, 7], [0, 1, 2, 6, 7], [0, 1, 2, 3, 6, 7], [0, 1, 2, 5, 6, 7], [0, 1, 2, 3, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7]$ 共 $9$ 个。 所以总共是 $2^6 - 9 = 55$ 种。

由 ChatGPT 5 翻译