C0413 [WC2014-A]时空穿梭

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

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

1. 每个点的每一维坐标均为正整数，且第 $𝑖$ 维坐标不超过 $𝑚_i$。
2. 第 $𝑖+1(1≤𝑖<𝑐)$ 个点的第 $𝑗(1≤𝑗≤𝑛)$ 维坐标必须严格大于第 $𝑖$ 个点的第 $𝑗$ 维坐标。
3. 存在一条直线经过所选的所有点。在这个 $𝑛$ 维空间里，一条直线可以用 $2𝑛$ 个实数 $𝑝_1,𝑝_2,...,𝑝_n,𝑣_1,𝑣_2,...,𝑣_n$ 表示。直线经过点 $(𝑥_1,𝑥_2,...,𝑥_n)$，当且仅当存在实数 $𝑡$，使得对 $𝑖=1...𝑛$ 均满足 $𝑥_i=𝑝_i+𝑡𝑣_i$。

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

样例输入 1

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

样例输出 1

2
4
846