P16419 [IATI 2022] Cubes

Octavia 的玩具中有 $N$ 个大小相同的立方体。这些立方体的重量可能不同，但也可能有两个立方体重量相同。Octavia 喜欢把她的立方体排成一个长序列，在玩了几个小时后，她开始琢磨能得到的不同的立方体序列有多少种。 立方体序列由 $N$ 个整数表示，其中每个整数对应初始序列中相应立方体的重量。Octavia 可以挑选两个相邻的立方体，只有当它们的总重量不超过整数 $K$ 时才能交换它们。Octavia 可以无限次地重复交换任意两个总重量不超过 $K$ 的相邻立方体。如果两个序列所对应的立方体重量序列不同，则认为这两个序列是不同的。 以 $4$ 个立方体、重量分别为 $[1, 2, 1, 3]$、$K = 3$ 的情况为例。可以获得的立方体序列共有 $3$ 种。第一种就是初始序列。要得到第二种序列，我们可以交换初始序列中第 $2$ 和第 $3$ 个位置上的立方体，从而得到序列 $[1, 1, 2, 3]$。注意，我们不能交换初始序列中第 $1$ 和第 $3$ 个位置上的立方体，因为它们不相邻。我们也不能交换第 $3$ 和第 $4$ 个位置上的立方体，因为它们的总重量为 $4$，大于 $K = 3$。最后一种序列可以通过交换初始序列中前两个立方体得到，即 $[2, 1, 1, 3]$。注意，如果从初始序列出发且 $K = 1$，则只有一种可能的序列；当 $K = 2$ 时，也只有一种；当 $K = 4$ 时，有 $6$ 种序列；当 $K = 5$ 时，有 $12$ 种序列。 请编写一个程序 $\texttt{cubes}$，帮助 Octavia 找出不同立方体序列的数量。

第一行有两个整数：$N$ —— 立方体的数量，以及 $K$ —— 可以交换的两个相邻立方体的最大总重量。第二行包含 $N$ 个正整数 $w_1, \cdots, w_N$，对应初始序列中各立方体的重量。

输出一行一个整数，表示 Octavia 可以得到的可能序列数，对 $1\,000\,000\,007$ 取模。

### 样例解释 **样例 1**：如题目描述中所示。 **样例 2**：我们只能交换重量为 $1$ 和 $3$ 的立方体，因此答案为 $2$，两种可能序列为 $[4, 3, 1, 5, 2]$ 和 $[4, 1, 3, 5, 2]$。 ### 数据范围 - $1 \leq N \leq 300\,000$ - $1 \leq w_i, K \leq 1\,000\,000\,000$ ### 子任务 | 编号 | 附加约束 | < | 分值 | |:----:|:--------------------------:|:---------:|:----:| | | $N$ | 其他 | | | 1 | $\leq 7$ | 所有重量互不相同 | 7 | | 2 | $\leq 100$ | 所有重量互不相同 | 23 | | 3 | $\leq 1000$ | 所有重量互不相同 | 15 | | 4 | $\leq 1000$ | – | 15 | | 5 | $\leq 100\,000$ | 所有重量互不相同 | 21 | | 6 | $\leq 300\,000$ | – | 19 | 翻译由 DeepSeek V4 Pro 完成