34505번 - Mashup 서브태스크다국어

문제

Nike Nirzayanov, the founder of the popular competitive typing platform SpeedForces, has recently added a new feature allowing users to create random mashups of past contests.

A contest on SpeedForces consists of $N$ implementation problems, each with a difficulty rating among $\{800,900,1000,1100,1200\}$. The $N$ problems in a single contest are always arranged in nondecreasing order of difficulty and assigned problem slots from 1ドル$ to $N$ in order.

Busy Beaver is testing out the new feature. He first specifies $N$ past contests, where the $i$-th contest he specifies has $a_{ij}$ problems of difficulty 800ドル+100(j-1)$ for each 1ドル \le j \le 5,ドル where $\sum_{j=1}^5 a_{ij} = N$.

The feature will select a random permutation $p_1,p_2,\dots,p_N$ of 1,2,ドル\dots,N$ and generate for Busy Beaver a contest where the $i$-th problem is the $i$-th problem in the $p_i$-th contest he specified.

Busy Beaver wonders: How many such permutations will result in a contest with reverse difficulty order (i.e., the problem difficulties are in nonincreasing order)? For some reason, he only wants the answer modulo 2.

입력

Each test contains multiple test cases. The first line contains the number of test cases $T$ (1ドル \leq T \leq 10^4$). The description of the test cases follows.

The first line of each test case contains the integer $N$ (1ドル \le N \le 2 \cdot 10^5$) --- the number of past contests and problems.

The next $N$ lines of each test case each contain 5ドル$ integers $a_{i1},a_{i2},a_{i3},a_{i4},a_{i5}$ ($a_{ij} \ge 0$ and $\sum_{j=1}^5 a_{ij} = N$).

It is guaranteed that the sum of $N$ across all test cases is no more than 2ドル \cdot 10^5$.

출력

For each test case, output a single integer, the number of such permutations modulo 2ドル$.

제한

서브태스크

노트

In the first test case, the $N = 3$ past contests have the following problem difficulties:

• Contest 1ドル$: 800,ドル 900, 900$.
• Contest 2ドル$: 900,ドル 900, 900$.
• Contest 3ドル$: 1000,ドル 1000, 1000$.

There are 2ドル$ permutations $p$ that result in a reverse difficulty order contest: $p = [3, 1, 2]$ and $p = [3, 2, 1]$. Therefore, the answer is 2ドル \bmod 2 = 0$.

In the second test case, the $N = 4$ past contests have the following problem difficulties:

• Contest 1ドル$: 800,ドル 800, 800, 800$.
• Contest 2ドル$: 800,ドル 900, 900, 900$.
• Contest 3ドル$: 900,ドル 900, 900, 1000$.
• Contest 4ドル$: 900,ドル 900, 1000, 1000$.

There are 3ドル$ permutations $p$ that result in a reverse difficulty order contest: $p = [3, 4, 2, 1],ドル $p = [4, 2, 3, 1],ドル and $p = [4, 3, 2, 1]$. Therefore, the answer is 3ドル \bmod 2 = 1$.

In the third test case, the only permutation $p = [1]$ generates a reverse difficulty order contest, so the answer is 1ドル \bmod 2 = 1$.