Description

The school organized a summer trip, and registration will close on day $T$.

There are $n$ students. Student $i$ has $a_i$ friends. The friendship relation is directed. In other words, if student Z has student Y as a friend, it does not mean student Y must have student Z as a friend. Also, a student may be their own friend.

On day $0$, each student decides whether to join the trip. Student $i$ decides to join with probability $p_i$, and decides not to join with probability $1-p_i$.

During the next $T$ days, each student will decide again whether to join. On that day, student $i$ decides to join if and only if at least one of their friends decided to join on the previous day; otherwise, they do not join.

You need to compute the expected number of students who join the trip. Output the answer modulo $998244353$.

Input Format

The first line contains two integers $n, T$, as described above.

The next $n$ lines each start with two integers $p_i, a_i$. Here, $p_i$ is the probability (under modulo $998244353$) that student $i$ decides to join on day $0$, and $a_i$ is the number of their friends. Then follow $a_i$ integers indicating their friends.

Output Format

Output one integer, the answer modulo $998244353$.

3 1
1 2 2 3
0 1 3
499122177 1 2

1

3 3
1 2 2 3
0 1 3
233 1 2

466

Hint

[Sample 1 Explanation]

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (3 points): $T = 0$.
• Subtask 2 (14 points): $T = 1$.
• Subtask 3 (33 points): $n \le 10$.
• Subtask 4 (20 points): $T \le 5 \times 10^3$.
• Subtask 5 (15 points): $n \le 100$.
• Subtask 6 (15 points): No special constraints.

For $100\%$ of the testdata: $1 \le n \le 500$, $0 \le T \le 10^9$, $0 \le p_i < 998244353$, $0 \le a_i \le n$, and all friends are distinct.

Translated by ChatGPT 5