XOR 행렬식

길이가 $n$인 두 배열 $b$와 $c$가 주어진다. 두 배열의 원소는 모두 음이 아닌 정수이다. $n \times n$ 행렬 $A$를 $A_{ij} = b_i \oplus c_j$로 정의한다. $A$의 행렬식을 $998244353$으로 나눈 나머지를 구한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 1000$)가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \le n \le 5000$)이 주어진다. 다음 줄에는 $b_1, b_2, \ldots, b_n$ ($0 \le b_i < 2^{60}$)이, 그 다음 줄에는 $c_1, c_2, \ldots, c_n$ ($0 \le c_i < 2^{60}$)이 주어진다. 모든 테스트 케이스의 $n$ 합은 $10000$을 넘지 않는다.

각 테스트 케이스마다 $A$의 행렬식을 $998244353$으로 나눈 나머지를 한 줄에 출력한다.

첫 번째 테스트 케이스: $\begin{vmatrix} 6 & 3 \\ 1 & 4 \end{vmatrix} = 6 \cdot 4 - 1 \cdot 3 = 21$이다. 두 번째 테스트 케이스는 $1 \times 1$ 행렬이므로 $\begin{vmatrix} 23792195055071677 \end{vmatrix} = 23792195055071677$이다. $998244353$으로 나눈 나머지는 $214139910$이다. 세 번째 테스트 케이스의 $\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$ $-224$를 $998244353$으로 나눈 나머지는 $998244129$이다.