Description

Beidajie is a very common place name in China. Well-known examples include Shanghai Beidajie, Xi'an Beidajie, Chengdu Beidajie, Taiyuan Beidajie, Zhongguancun Beidajie, etc.

We all know that “Bei” means freedom and democracy, and “Da” means being inclusive, so the people living on Beidajie also have very different personalities. Suppose there are $n$ people living on Beidajie.

Someone asked these $n$ people $n-1$ questions, for example:

• “Do you use chopsticks?”
• “Do you eat braised pork?”
• “Do you use tab or space when writing code?”
• “Do you put the curly brace on a new line?”
• “...”

Based on each person's answers, they will be assigned an $(n-1)$-dimensional binary coordinate, i.e., a point. In this way, these $n$ points can form exactly the convex hull in an $(n-1)$-dimensional space.

The residents of Beidajie believe that inside this polytope is Huaxia, and outside the polytope is barbarian land. We can easily compute the generalized convex hull volume of the Huaxia part.

One day, Mr. B from Qinghua Road came to Beidajie to have fun. He found this story interesting, so he also tried to provide answers to these $n-1$ questions.

Mr. B from Qinghua Road, of course, thinks he belongs to Huaxia, but Beidajie says that in an $(n-1)$-dimensional space, if there are $n+1$ points, then the volume of the Huaxia part is hard to compute.

The atmosphere suddenly became awkward. So this problem is left to you: given $n+1$ points in an $(n-1)$-dimensional space, find the volume of their generalized convex hull.

Since this volume may not be an integer, you only need to output the result of multiplying the volume by $(n-1)!$, and then taking it modulo $10^9+7$.

Input Format

Read input from standard input.

The first line contains an integer $T$, indicating the number of test cases. Then follow $T$ test cases.

For each test case, the first line contains an integer $n$.

The next $n+1$ lines each contain $n-1$ integers, representing a point in an $(n-1)$-dimensional space.

Output Format

Write output to standard output.

For each test case, output one line with one integer, the answer.

Output the convex hull volume of the $n+1$ input points multiplied by $(n-1)!$, and then taken modulo $10^9+7$.

1
3
0 0
0 1
1 0
1 1

2

Hint

$1\le t\le 100,3\le n\le35$.

Each coordinate of every point is guaranteed to be $0$ or $1$.

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017.

Translated by ChatGPT 5