题目描述

Octavia 有 N 个大小相同的方块。方块的重量可能不同，也可能有多个方块重量相同。

她把这些方块排成一个长序列。序列可以用 N 个整数表示，其中第 i 个整数表示第 i 个方块的重量。

Octavia 可以进行如下操作任意多次：

• 选择两个相邻的方块；
• 若它们的重量之和 不大于 整数 K，则可以交换这两个方块的位置。

如果两个序列对应位置上的重量序列不同，则认为它们是不同的序列。

现在请你求出：通过若干次合法交换后，一共能得到多少种不同的方块序列。

说明

例如，N=4，初始序列为 [1,2,1,3]，K=3。

此时一共可以得到 3 种不同序列：

• 初始序列 [1,2,1,3]；
• 交换第 2、3 个方块，得到 [1,1,2,3]；
• 交换第 1、2 个方块，得到 [2,1,1,3]。

注意：

• 不能交换位置 1 和 3 的方块，因为它们不相邻；
• 不能交换位置 3 和 4 的方块，因为 1+3=4>K。

同样地：

• 当 K=1 时，只能得到 1 种序列；
• 当 K=2 时，也只能得到 1 种序列；
• 当 K=4 时，可以得到 6 种序列；
• 当 K=5 时，可以得到 12 种序列。

输入格式

第一行包含两个整数 N, K，表示方块数量，以及允许交换的相邻两个方块重量和的最大值。

第二行包含 N 个正整数 w_1, w_2, ..., w_N，表示初始序列中各方块的重量。

输出格式

输出一行一个整数，表示不同序列的数量。答案对 1 000 000 007 取模。

样例 #1

输入 #1

4 5
1 2 1 3

输出 #1

12

样例 #2

输入 #2

5 4
4 3 1 5 2

输出 #2

2

样例解释

对于样例 #1，见题目描述。

对于样例 #2，只能交换重量为 3 和 1 的两个方块，因此答案为 2。两种可能序列为：

• [4,3,1,5,2]
• [4,1,3,5,2]

数据范围

• 1 <= N <= 300000
• 1 <= w_i, K <= 10^9

子任务

只有通过某个子任务的所有测试点，才能获得该子任务的分数。