시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 5 4 3 75.000%

## 문제

Assuming people numbered from $1$ to $2n$ are assigned to two teams of size $n$ using the following non-deterministic procedure, find the probability that all people from the set $A^i = \{a^i_1, a^i_2, \dots , a^i_{k_i}\}$ end up on the same team, for each of the given sets $A^1, A^2, \dots , A^m$, and 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 which case the person joins the second team;
• similarly, if the coin lands tails up, the person joins the second team unless that team already has $n$ people, in which 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$ and 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 $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 sought probability can be represented as an irreducible fraction $\frac{p}{q}$ such that $q \not\equiv 0 \mod{998 244 353}$. Then, there exists a unique integer $r$ such that $r \cdot q \equiv p \mod {998 244 353}$ and $0 \le r < 998 244 353$, so display this $r$.

## 예제 입력 1

2 6
2 1 2
2 1 3
2 1 4
2 2 3
2 2 4
2 3 4


## 예제 출력 1

499122177
748683265
748683265
748683265
748683265
499122177


## 예제 입력 2

3 5
3 2 3 5
2 2 4
2 5 6
3 1 4 6
2 2 5


## 예제 출력 2

935854081
623902721
374341633
935854081
686292993


## 힌트

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}$.