교차하는 경로

정점을 $k$개의 레벨로 나눌 수 있는 방향 그래프가 있다. 레벨 $i$에는 $n_i$개의 정점이 있고, 레벨 $1$과 레벨 $k$의 정점 수는 같다. 즉 $n_1=n_k$이다. 각 레벨 $j$ $(2 \le j \le k-1)$에 대해서는 $n_1 \le n_j \le 2n_1$이다. 레벨 $j$ $(1 \le j < k)$의 정점을 꼬리로 하는 간선은 레벨 $j+1$의 정점만을 머리로 한다. 레벨 $1$의 정점을 머리로 하는 간선은 없고, 레벨 $k$의 정점을 꼬리로 하는 간선도 없다.

이제 $n_1$개의 경로로 이루어진 집합을 고르려고 한다. 집합의 각 경로는 레벨 $1$의 정점에서 시작해 레벨 $k$의 정점에서 끝나며, 한 정점은 둘 이상의 경로에 포함될 수 없다. 더 형식적으로, 각 레벨의 정점을 $1,2,\dots,n_i$로 번호를 붙이면 각 경로는 $k$-튜플 $(p_1,p_2,\dots,p_k)$로 나타낼 수 있다. 이는 경로가 레벨 $j$에서 정점 $p_j$ $(1 \le p_j \le n_j)$를 지나며, 각 $j$ $(1 \le j < k)$에 대해 레벨 $j$의 정점 $p_j$에서 레벨 $j+1$의 정점 $p_{j+1}$로 가는 간선이 있음을 뜻한다.

경로를 종이에 그리면 교차점이 생긴다. 경로 $P,Q$에 대해, 레벨 $j$와 레벨 $j+1$ 사이에서 두 경로가 지나는 간선이 각각 $(P_j,P_{j+1})$, $(Q_j,Q_{j+1})$이고 $(P_j-Q_j)\times(P_{j+1}-Q_{j+1})<0$이면, 두 경로가 레벨 $j$에서 교차한다고 한다. 두 경로의 교차점 수는 레벨 $1$부터 레벨 $k-1$까지에서 생기는 교차점 수의 합이다. 경로 집합의 교차점 수는 서로 다른 두 경로 사이의 교차점 수를 모두 합한 값이다. 아래 예에서는 경로 3개가 교차점 3개를 만든다. 빨간 점이 교차점이다.

이제 교차점 수가 짝수인 경로 집합의 수에서 교차점 수가 홀수인 경로 집합의 수를 뺀 값을 구하려고 한다. 두 경로 집합은 $n_1$개의 경로에 대응하는 $k$-튜플의 모음이 같을 때, 그리고 그때만 같은 집합으로 본다. 경로 집합은 집합이므로 경로의 순서는 고려하지 않는다. 결과가 클 수 있으므로 소수 $998\,244\,353$으로 나눈 나머지를 출력한다.

한 입력 파일에 여러 테스트 케이스가 들어 있다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 레벨의 수 $k$가 주어진다.

둘째 줄에는 $k$개의 정수 $n_1,n_2,\dots,n_k$가 주어지며, 각 레벨의 정점 수를 나타낸다. $n_1=n_k$이고 $2 \le i \le k-1$인 모든 $i$에 대해 $n_1 \le n_i \le 2n_1$임이 보장된다.

셋째 줄에는 $k-1$개의 정수 $m_1,m_2,\dots,m_{k-1}$이 주어지며, 레벨 $j$의 정점과 레벨 $j+1$의 정점 사이의 간선 수를 나타낸다. $m_j \le n_j \times n_{j+1}$임이 보장된다.

이어서 $k-1$개의 입력 묶음이 주어진다. $j$번째 묶음 $(1 \le j < k)$에는 $m_j$개의 줄이 있다. 각 줄에는 두 정수 $u,v$가 주어지며, 레벨 $j$의 정점 $u$에서 레벨 $j+1$의 정점 $v$로 가는 간선이 있음을 나타낸다.

평행 간선은 없음이 보장된다.

출력은 $T$줄이다. 각 줄에는 교차점 수가 짝수인 경로 집합의 수에서 홀수인 경로 집합의 수를 뺀 값을 $998\,244\,353$으로 나눈 나머지를 출력한다.

모든 테스트 세트에 대해 $2 \le k \le 100$, $2 \le n_i \le 100$, $1 \le T \le 5$이다. 각 테스트 세트에는 $n_1>10$인 테스트 케이스가 최대 하나뿐임이 보장된다.

교차점 수가 짝수인 경로 집합이 2개, 홀수인 경로 집합이 1개이므로 답은 1이다.

집합 1에서 두 경로는 $k$-튜플 표기로 $(1,1,2)$와 $(2,3,1)$이다. 교차점은 모두 1개다. 두 경로를 바꾸어도 같은 경로 집합이 되며, 같은 집합을 두 번 세지 않는다.

집합 2에서 두 경로는 $(1,2,1)$과 $(2,1,2)$이다. 교차점은 2개다.

집합 3에서 두 경로는 $(1,2,1)$과 $(2,3,2)$이다. 교차점은 0개다.