cho.sh

XOR Determinant

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

You are given two arrays bb and cc of length nn, consisting of non-negative integers. Construct n×nn \times n matrix AA as A_ij=b_i⊕c_jA\_{ij} = b\_i \oplus c\_j. Find the determinant of AA modulo 998,244,353998\\,244\\,353.

입력

Each test contains multiple test cases. The first line contains an integer tt (1≤t≤10001 \le t \le 1000) --- the number of test cases. The descriptions of the tt test cases follow.

The first line of each test case contains one integer nn (1≤n≤50001 \le n \le 5000).

The second line contains the array b_1,b_2,…,b_nb\_1, b\_2, \ldots, b\_n (0≤b_i<2600 \le b\_i < 2^{60}).

The third line contains the array c_1,c_2,…,c_nc\_1, c\_2, \ldots, c\_n (0≤c_i<2600 \le c\_i < 2^{60}).

The sum of nn over all test cases does not exceed 10,00010\\,000.

출력

For each test case, print the determinant of matrix AA modulo 998,244,353998\\,244\\,353.

힌트

First test case:

∣63 14∣=6⋅4−1⋅3=21\begin{vmatrix} 6 & 3\\\ 1 & 4 \end{vmatrix} = 6 \cdot 4 - 1 \cdot 3 = 21

Second test case:

∣23,792,195,055,071,677∣=23,792,195,055,071,677\begin{vmatrix} 23\\,792\\,195\\,055\\,071\\,677 \end{vmatrix} = 23\\,792\\,195\\,055\\,071\\,677

23,792,195,055,071,677 mod 998,244,353=214,139,91023\\,792\\,195\\,055\\,071\\,677 \bmod 998\\,244\\,353 = 214\\,139\\,910

Third test case:

∣0325 3016 2107 5670∣=3⋅3⋅7⋅7−3⋅1⋅7⋅5−3⋅6⋅2⋅7−2⋅3⋅7⋅6+2⋅6⋅2⋅6−2⋅6⋅1⋅5−5⋅3⋅1⋅7−5⋅1⋅2⋅6+5⋅1⋅1⋅5=\begin{vmatrix} 0 & 3 & 2 & 5 \\\ 3 & 0 & 1 & 6 \\\ 2 & 1 & 0 & 7 \\\ 5 & 6 & 7 & 0 \end{vmatrix} = 3 \cdot 3 \cdot 7 \cdot 7 - 3 \cdot 1 \cdot 7 \cdot 5 - 3 \cdot 6 \cdot 2 \cdot 7 - 2 \cdot 3 \cdot 7 \cdot 6 + 2 \cdot 6 \cdot 2 \cdot 6 - 2 \cdot 6 \cdot 1 \cdot 5 - 5 \cdot 3 \cdot 1 \cdot 7 - 5 \cdot 1 \cdot 2 \cdot 6 + 5 \cdot 1 \cdot 1 \cdot 5 =

=441−105−252−252+144−60−105−60+25=−224= 441 - 105 - 252 - 252 + 144 - 60 - 105 - 60 + 25 = -224

(−224) mod 998,244,353=998,244,129(-224) \bmod 998\\,244\\,353 = 998\\,244\\,129