AT_s8pc_4_e Enormous Atcoder Railroad

[问题链接]: https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_e 给你 $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 翻译