Travel

Alice is currently traveling in a $k$-dimensional space. She starts at $(0,0,\ldots,0)$, and she has a total of $n$ teleportation skills. When she uses a teleportation skill, if she is at $(x_1,x_2,\ldots,x_k)$ and the teleportation skill is $(y_1,y_2,\ldots,y_k)$, she will be teleported to $(x_1+y_1,\ldots,x_k+y_k)$. Teleportation skills can be used in any way.

This $k$-dimensional space is finite, and the size of the $i$-th dimension is $N_i$. In other words, for the $i$-th dimension, the coordinate range is $0\le x_i \le N_i$.

Alice's destination is $(N_1,\ldots,N_k)$. There are a total of $m$ black holes in the $k$-dimensional space, which means Alice cannot reach those positions in any way. Alice wants to know how many ways she can use teleportation skills to reach her destination without passing through any black holes.

We consider two different teleportation plans to be different if and only if there exists a step where the two plans use different teleportation skills.

Two teleportation skills are considered different if and only if their skill numbers are different. Even if the effects of these two skills are exactly the same, they will still be considered as two separate skills.

Since the answer can be large, please output it modulo $998244353$.

The input consists of multiple test cases. The first line contains a single integer $T(1≤T≤5)$ — the number of test cases. Description of the test cases follows.

The first line of each test case contains one integers $k$ $(2≤k≤16) $—This means that the space has a total of $k $dimensions.

The next line contains $k$ positive integers $N_i$ $(1\le N_i\le 10^5)$, representing the size of the $i$-th dimension.

The next line contains two integers $n$ and $m$ , $(1\le n \le 10^5 , 0\le m\le 1000)$ , representing the number of teleportation skills and the number of obstacles, respectively.

The next $n$ lines contain $k$ non-negative integers $(y_1,\ldots,y_k)$, where $(\forall i \in [1 , k], 0\le y_i\le N_i)$, representing the current teleportation skills.

The next $m$ lines contain $k$ non-negative integers $(x_1,\ldots,x_k)$, where $(\forall i \in [1 , k], 0\le x_i\le N_i)$, representing the coordinates of the black holes.

It is guaranteed that there is no leap skill corresponding to $(0,0,\cdots,0)$.

The data ensures that $\prod_{i=1}^{k} (N_i+1) \leq 2\times 10^5$.

For each test case, output an integer representing the number of ways Alice can reach her destination modulo 998244353.

1
2
100 1000
2 0
1 0
0 1

555294450

2023“钉耙编程”中国大学生算法设计超级联赛（1）