J. Joining Arrays
time limit per test
30 с
memory limit per test
256 megabytes
input
standard input
output
standard output

Define the permutation scaling of an array $$$[B_1, B_2, \dots, B_m]$$$ as the unique permutation $$$P$$$ of $$$[1, 2, 3, \dots, m]$$$ such that for each pair of indices $$$1 \le i \lt j \le m$$$, $$$P_i \lt P_j$$$ if and only if $$$B_i \le B_j$$$. For example, the permutation scaling of the array $$$[2,1,1,5,8,3]$$$ is $$$[3,1,2,5,6,4]$$$.

There are $$$n$$$ sets of integers $$$S_1, S_2, \dots, S_n$$$. An array $$$[A_1, A_2, \dots, A_n]$$$ is formed by choosing one element from each set, that is, $$$A_i \in S_i$$$ for $$$i = 1, 2, \dots, n$$$.

How many ways are there to choose the elements such that the permutation scaling of $$$A$$$ is lexicographically maximal?

Input

The first line of input contains an integer $$$n$$$ ($$$1 \le n \le 5 \times 10^5$$$).

Then the descriptions of $$$S_1, S_2, \dots, S_n$$$ follow. The description of each set $$$S_i$$$ contains two lines. The first line contains an integer $$$k_i$$$, the size of $$$S_i$$$ ($$$1 \le k_i \le 5 \times 10^5$$$). The second line contains $$$k_i$$$ distinct integers $$$s_1, s_2, \dots, s_{k_i}$$$, the elements of $$$S_i$$$ ($$$1 \le s_j \le 10^9$$$).

It is guaranteed that $$$\sum_{i=1}^n k_i \le 5 \times 10^5$$$.

Output

Print one integer — the number of ways. Since it can be very large, output it modulo $$$998244353$$$.

Examples
Input
4
5
7 11 3 10 1
3
8 6 4
1
15
3
1 5 99
Output
13
Input
4
2
2 1
3
5 1 6
1
3
3
6 5 7
Output
3
Note

In the first example, the lexicographically maximal permutation scaling is $$$[3, 2, 4, 1]$$$ and there are 13 different ways to choose the array $$$A$$$: $$$[7,4,15,1]$$$, $$$[7,6,15,1]$$$, $$$[7,6,15,5]$$$, $$$[10,4,15,1]$$$, $$$[10,6,15,1]$$$, $$$[10,6,15,5]$$$, $$$[10,8,15,1]$$$, $$$[10,8,15,5]$$$, $$$[11,6,15,1]$$$, $$$[11,6,15,5]$$$, $$$[11,8,15,1]$$$ and $$$[11,8,15,5]$$$.

In the second example, the lexicographically maximal permutation scaling is $$$[2, 1, 3, 4]$$$ and there are 3 different ways to choose the array $$$A$$$: $$$[2,1,3,5]$$$, $$$[2,1,3,6]$$$ and $$$[2,1,3,7]$$$.