给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\cdots,a_n$，以及一个正整数 $R$。

请你求出，有多少种长度为 $n$ 的正整数序列 $b_1,b_2,\cdots,b_n$，满足：

• 对于任意 $1 \le i \le n$，有 $a_i \le b_i \le R$。
• 对于任意 $1 \le i < n$，有 $b_i \ge b_{i+1}$。

答案对 $10^9+7$ 取模。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T$ $(1 \le T \le 10)$，表示数据组数。

对于每组测试数据：

• 第一行两个正整数 $n,R$ $(1 \le n \le 5 \times 10^3, 1 \le R \le 10^9)$，分别表示序列长度与限制条件。
• 第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ $(1 \le a_i \le R)$，表示序列 $a$。

保证所有测试数据中 $n$ 之和不超过 $5.2 \times 10^3$。

输出格式

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

样例

输入

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

输出

6
917124963

提示

对于样例一，有 $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]$