计数

Problem Description

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \cdots, a_n$，以及一个正整数 $R$。 请你求出，有多少种长度为 $n$ 的正整数序列 $b_1, b_2, \cdots, b_n$，满足：

• 对于任意 $1 \leq i \leq n$，有 $a_i \leq b_i \leq R$。
• 对于任意 $1 \leq i < n$，有 $b_i \geq b_{i + 1}$。 答案对 $10^9 + 7$ 取模。

Input

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T(1 \leq T \leq 10)$，表示数据组数。对于每组测试数据： 第一行两个正整数 $n, R(1 \leq n \leq 5 \times 10^3, 1 \leq R \leq 10^9)$，分别表示序列长度与限制条件。 第二行 $n$ 个正整数 $a_1, a_2, \cdots, a_n(1 \leq a_i \leq R)$，表示序列 $a$。 保证所有测试数据中 $n$ 之和不超过 $5.2 \times 10^3$。

Output

对于每组测试数据：输出一行一个整数，表示答案对 $10^9 + 7$ 取模后的值。

Sample Input

2
5 5
3 1 3 4 4
4 1000
1 1 1 1

Sample Output

6
917124963

Hint

对于样例一，有 $6$ 种合法的 $b$ 序列：

• $b = [5, 5, 5, 5, 5]$。
• $b = [5, 5, 5, 5, 4]$。
• $b = [5, 5, 5, 4, 4]$。
• $b = [5, 5, 4, 4, 4]$。
• $b = [5, 4, 4, 4, 4]$。
• $b = [4, 4, 4, 4, 4]$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（2）