小 X 驾驶着他的飞船准备穿梭过一个 $n$ 维空间，这个空间里每个点的坐标可以用 $n$ 个实数表示，即 $(x_1,x_2,\dots ,x_n)$。

为了穿过这个空间，小 X 需要在这个空间中选取 $c$（$c\ge 2$）个点作为飞船停留的地方，而这些点需要满足以下三个条件：

1. 每个点的每一维坐标均为正整数，且第 $i$ 维坐标不超过 $m_i$。
2. 第 $i+1$（$1\le i<c$）个点的第 $j$（$1\le j\le n$）维坐标必须严格大于第 $i$ 个点的第 $j$ 维坐标。
3. 存在一条直线经过所选的所有点。在这个 $n$ 维空间里，一条直线可以用 $2n$ 个实数 $p_1,p_2,\dots ,p_n,v_1,v_2,\dots ,v_n$ 表示。直线经过点 $(x_1,x_2,\dots ,x_n)$，当且仅当存在实数 $t$，使得对 $i=1\dots n$ 均满足 $x_i=p_i+t{v}_i$。

小 X 还没有确定他的最终方案，请你帮他计算一下一共有多少种不同的方案满足他的要求。由于答案可能会很大，你只需要输出答案 $mod10007$ 后的值。

输入格式

第一行包含一个正整数 $T$，表示有 $T$ 组数据需要求解。

每组数据包含两行，第一行包含两个正整数 $n,c$（$c\ge 2$），分别表示空间的维数和需要选择的暂停点的个数。

第二行包含 $n$ 个正整数，依次表示 $m_1,m_2,\dots ,m_n$。

输出格式

共 $T$ 行，每行包含一个非负整数，依次对应每组数据的答案。

样例一

input

3
2 3
3 4
3 3
3 4 4
4 4
5 9 7 8

output

2
4
846

explanation

对于第一组数据，共有两种可行的方案：一种选择 $(1,1),(2,2),(3,3)$，另一种选择 $(1,2),(2,3),(3,4)$。

样例二

见样例数据下载。

限制与约定

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载