题目描述

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$ 取模。

4 5
1 2 1 3

12

5 4
4 3 1 5 2

2

提示

样例解释

样例 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$

子任务

翻译由 DeepSeek V4 Pro 完成