暂无测试数据。

题目描述

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

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

1. 每个点的每一维坐标均为正整数，且第 \(i\) 维坐标不超过。

2. 第 \(i+1\) ( \(1 \leq i \leq c\) ) 个点的第 \(j\) \((1 \leq j \leq n)\) 维坐标必须严格大于第 \(i\) 个点的第 \(j\) 维坐标。

3. 存在一条直线经过所选的所有点。
在这个 \(n\) 维空间里，
一条直线可以用 \(2n\) 个实数 \(p_1,p_2,\cdots,p_n,v_1,v_2,\cdots,v_n\) 表示。
直线经过点 \((x_1,x_2,\cdots,x_n)\)，
当且仅当存在实数 \(t\)，
使得对 \(i=1,2,\cdots,n\) 均满足 \(x_i=p_i+tv_i\)。

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

输入

第一行，一个正整数 \(T\)，
表示有 \(T\) 组数据需要求解。

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

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

输出

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

样例输入

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

样例输出

2
4
846

数据范围限制

来源

WC2014