Flip

Assume people numbered from $1$ to $2n$ are assigned to two teams of size $n$ using the following procedure. Find, for each given set $A^1, A^2, \dots, A^m$, the probability that all people in that set end up on the same team. Display it modulo 998 244 353.

• In order from $1$ to $2n$, each person flips a fair coin.
• If the coin lands heads up, the person joins the first team, unless that team already has $n$ people. In that case, the person joins the second team.
• If the coin lands tails up, the person joins the second team, unless that team already has $n$ people. In that case, the person joins the first team.

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$; $1 \le m \le 10^5$).

The $i$-th of the next $m$ lines describes set $A^i$. It contains an integer $k_i$ ($2 \le k_i \le n$), followed by $k_i$ integers $a^i_1, a^i_2, \dots, a^i_{k_i}$ ($1 \le a^i_1 < a^i_2 < \dots < a^i_{k_i} \le 2n$).

The sum of all $k_i$ does not exceed $2 \cdot 10^5$.

For each $i$ from $1$ to $m$, display the probability that all people from the set $A^i$ end up on the same team.

It can be shown that any such probability can be written as an irreducible fraction $\frac{p}{q}$ with $q \not\equiv 0 \pmod{998\,244\,353}$. Then there is a unique integer $r$ with $r \cdot q \equiv p \pmod{998\,244\,353}$ and $0 \le r < 998\,244\,353$. Display this $r$.

In the first test case, people $1$ and $2$ (and people $3$ and $4$) end up on the same team with probability $\frac{1}{2}$. For any other pair, the probability is $\frac{1}{4}$.