Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

[WC2014]时空穿梭

题目描述

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

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

$1$. 每个点的每一维坐标均为正整数,且第 $i$ 维坐标不超过 $m_i$ 。

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

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

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

输入格式

输入文件 space.in 的第一行包含一个正整数 $T$ ,表示有 $T$ 组数据需要求解。

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

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

输出格式

输出文件 space.out 包含 $T$ 行,每行包含一个非负整数,依次对应每组数据

的答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
4
846

样例 #2

样例输入 #2

1
11 20
97665 99289 91440 92389 93960 94623 96582 93975 98359 93492 90331

样例输出 #2

3278

样例

提示

【样例$1$说明】

样例数据第一组共有两种可行方案:一种是选择 $(1,1)$ , $(2,2)$ , $(3,3)$ ,另一种是选择 $(1,2)$ , $(2,3)$ , $(3,4)$ 。

【数据规模】

测试点编号 $T$ $n$ $c$ $m_i$
1 $= 1000$ $= 1$ $\leq 20$ $\leq 100000$
2 $= 3$ $\leq 4$ $\leq 20$ $\leq 30$
3 $= 3$ $= 2$ $= 3$ $\leq 100000$
4 $= 1000$ $= 2$ $= 3$ $\leq 100000$
5 $= 20$ $\leq 5$ $= 3$ $\leq 100000$
6 $= 100$ $\leq 11$ $= 3$ $\leq 100000$
7 $= 1$ $\leq 5$ $\leq 20$ $\leq 100000$
8 $= 20$ $\leq 5$ $\leq 20$ $\leq 100000$
9 $= 100$ $\leq 11$ $\leq 20$ $\leq 100000$
10 $= 100$ $\leq 11$ $\leq 20$ $\leq 100000$