Occurrences codeforces solution- A subarray of array aa from index ll to the index rr is the array [al,al+1,…,ar][al,al+1,…,ar]. The number of occurrences of the array bb in the array aa is the number of subarrays of aa such that they are equal to bb.

Occurrences solution codeforces

A subarray of array aa from index ll to the index rr is the array [al,al+1,,ar][al,al+1,…,ar]. The number of occurrences of the array bb in the array aa is the number of subarrays of aa such that they are equal to bb.

You are given nn arrays A1,A2,,AnA1,A2,…,An; the elements of these arrays are integers from 11 to kk. You have to build an array aa consisting of mm integers from 11 to kk in such a way that, for every given subarray AiAi, the number of occurrences of AiAi in the array aa is not less than the number of occurrences of each non-empty subarray of AiAi in aa. Note that if AiAi doesn’t occur in aa, and no subarray of AiAi occurs in aa, this condition is still met for AiAi.

Your task is to calculate the number of different arrays aa you can build, and print it modulo 998244353998244353.

Occurrences solution codeforces

The first line contains three integers nnmm and kk (1n,m,k31051≤n,m,k≤3⋅105) — the number of the given arrays, the desired length of the array aa, and the upper bound on the values in the arrays.

Then nn lines follow. The ii-th line represents the array AiAi. The first integer in the ii-th line is cici (1cim1≤ci≤m) — the number of elements in AiAi; then, cici integers from 11 to kk follow — the elements of the array AiAi.

Additional constraint on the input: i=1nci3105∑i=1nci≤3⋅105; i. e., the number of elements in the given arrays in total does not exceed 31053⋅105.

Occurrences solution codeforces

Print one integer — the number of different arrays aa you can build, taken modulo 998244353998244353.

Examples

input

Copy
2 4 3
2 1 2
1 3

output

Copy
5

Occurrences solution codeforces

Copy
2 4 3
2 1 2
3 3 2 1

output

Copy
0

input

Copy
1 42 1337
2 13 31

output

Copy
721234447

Leave a Comment