410613: GYM104065 I Mental Abuse To Humans

Bobo is asked to solve the following math problem:

Given $$$m$$$ pairs of integers $$$(x_1,t_1),(x_2,t_2),\ldots,(x_m,t_m)$$$ where $$$0 \leq x_i < n$$$ and $$$t_i\in \{0,1\}$$$, count the number of subsets $$$A \subseteq S_n=\{0,1,\dots,n-1\}$$$ satisfying

• $$$\forall 1 \le i \le m$$$, $$$x_i \in A$$$ if and only if $$$t_i = 1$$$.
• $$$ A +_n (S_n \setminus A) = S_n$$$.

For any two sets $$$A,B$$$ consisting of nonnegative integers, $$$A+_n B$$$ is defined by $$$$$$A+_n B = \{(a+b) \bmod n \mid a \in A, b \in B\}.$$$$$$

The answer might be enormous, and you should output the answer modulo $$$998\,244\,353$$$.

Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 5$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le m \le 5$$$), denoting the size of the universe and the number of integer pairs, respectively.

Then $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$x_i,t_i$$$ ($$$0 \le x_i <n, t_i \in \{0,1\}$$$), describing the $$$i$$$-th integer pair.

It is guaranteed that $$$x_1,x_2,\ldots,x_m$$$ are pairwise distinct.

For each test case, output a single integer, denoting the desired answer modulo $$$998\,244\,353$$$.

2
3 0
6 2
0 0
1 1

0
4