P7429 [THUPC 2017] 气氛

北大街，在中国是一个非常常见的地名，比较著名的有上海北大街，西安北大街，成都北大街，太原北大街，中关村北大街等。 我们都知道，北的意思是自由民主，大的意思是兼收并蓄，所以住在北大街的人也性情迥异，我们假设在北大街住了 $n$ 个人。 有人向住在北大街的这 $n$ 个人提了 $n-1$ 个问题，比如： 「用不用筷子？」 「吃不吃红烧肉？」 「写代码用 tab 还是 space」 「大括号换不换行？」 「……」 根据每个人的回答，他会被分配一个 $n-1$ 维的零一坐标，也就是一个点。这样 $n$ 个点可以恰好构成一个 $n-1$ 维空间中的凸包。 北大街的居民认为，在这个多面体内，便是华夏；多面体之外，便是蛮夷。我们可以很容易的计算出华夏部分的广义凸包体积。 有一天，清华路的 B 君来北大街玩，听说了这个故事觉得很有趣，于是也试着给出了这 $n-1$ 个问题的答案， 清华路的 B 君，当然认为自己属于华夏，但是北大街表示在 $n-1$ 维空间中如果有 $n+1$ 个点的话，华夏部分的体积难以计算。 这下子气氛突然僵化。所以这个问题就留给你了，输入 $n-1$ 维度空间中的 $n+1$ 个点，求广义凸包的体积。 由于这个体积可能不是整数，你只需要输出体积乘以 $n-1$ 的阶乘，然后对 $10^9+7$ 取模的结果。

从标准输入读入数据。 第一行一个整数 $T$ 表示组数，接下来是 $T$ 组数据 每组数据的第一行是一个整数 $n$ 。 接下来 $n+1$ 行，每行 $n-1$ 个整数，表示在 $n-1$ 维空间中的一个点。

输出到标准输出。 对于每组数据，输出一行一个整数表示答案。 输入 $n+1$ 个点的凸包体积乘以 $n-1$ 的阶乘，然后对 $10^9+7$ 取模的结果。

$1\le t\le 100,3\le n\le35$ 点的坐标一定是 $0$ 或者 $1$。 #### 版权信息 来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2017。