题目描述
Problem Description
The school has organized a summer outing activity, with registration closing on the $T$-th day.
There are $n$ students, and the $i$-th student has $a_i$ friends. The friendship is unidirectional, meaning that if Student Z has a friend Y, it does not necessarily mean that Y also has a friend Z. Additionally, a student can be a friend of themselves.
On the $0$-th day, each student decides whether to participate in the activity. The $i$-th student has a probability of $p_i$ to decide to participate and a probability of $1-p_i$ to decide not to participate.
Over the next $T$ days, each student will reconsider whether to participate in the activity. The $i$-th student decides to participate on a given day if and only if at least one of their friends decided to participate the previous day, otherwise they do not participate.
You need to calculate the expected number of students participating in the activity, modulo $998244353$.
Input Format
The first line contains two integers $n$ and $T$, as described in the problem statement.
The next $n$ lines each start with two integers $p_i$ and $a_i$. $p_i$ represents the probability, modulo $998244353$, that the $i$-th student decides to participate on the $0$-th day, and $a_i$ represents the number of friends they have. This is followed by $a_i$ integers indicating their friends.
Output Format
A single line containing an integer, representing the answer modulo $998244353$.
Sample Input and Output
Sample Input #1
3 1
1 2 2 3
0 1 3
499122177 1 2
Sample Output #1
1
Sample Input #2
3 3
1 2 2 3
0 1 3
233 1 2
Sample Output #2
466
Notes
[Sample 1 Explanation]
| Day | Probability of First Student | Probability of Second Student | Probability of Third Student |
|---|---|---|---|
| $0$ | $1$ | $0$ | $\frac{1}{2}$ |
| $1$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $0$ |
[Data Range]
This problem is bundled with subtasks.
- 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 restrictions.
For $100\%$ of the data, $1 \le n \le 500$, $0 \le T \le 10^9$, $0 \le p_i < 998244353$, $0 \le a_i \le n$ and friends are distinct.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分