18747번 - Flip 다국어

문제

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\).

제한

힌트

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}\).