description: A subarray of array a from index l to the index r is the array [a_l, a_{l+1}, ..., a_{r}]. The number of occurrences of the array b in the array a is the number of subarrays of a such that they are equal to b.
  
  You are given n arrays A_1, A_2, ..., A_n; the elements of these arrays are integers from 1 to k. You have to build an array a consisting of m integers from 1 to k in such a way that, for every given subarray A_i, the number of occurrences of A_i in the array a is not less than the number of occurrences of each non-empty subarray of A_i in a. Note that if A_i doesn't occur in a, and no subarray of A_i occurs in a, this condition is still met for A_i.
  
  Your task is to calculate the number of different arrays a you can build, and print it modulo 998244353.
  
  Input
  
  The first line contains three integers n, m and k (1 ≤ n, m, k ≤ 3 ⋅ 10^5) — the number of the given arrays, the desired length of the array a, and the upper bound on the values in the arrays.
  
  Then n lines follow. The i-th line represents the array A_i. The first integer in the i-th line is c_i (1 ≤ c_i ≤ m) — the number of elements in A_i; then, c_i integers from 1 to k follow — the elements of the array A_i.
  
  Additional constraint on the input: ∑_{i=1}^n c_i ≤ 3 ⋅ 10^5; i. e., the number of elements in the given arrays in total does not exceed 3 ⋅ 10^5.
  
  Output
  
  Print one integer — the number of different arrays a you can build, taken modulo 998244353.
  
  Examples
  
  Input
  
  
  2 4 3
  2 1 2
  1 3
  
  
  Output
  
  
  5
  
  
  Input
  
  
  2 4 3
  2 1 2
  3 3 2 1
  
  
  Output
  
  
  0
  
  
  Input
  
  
  1 42 1337
  2 13 31
  
  
  Output
  
  
  721234447
solution: #include <bits/stdc++.h>
  #pragma GCC optimize("O3")
  #pragma GCC target("tune=native")
  #pragma GCC optimize("unroll-loops")
  using namespace std;
  const int MAX = 1e6 + 5;
  const long long MOD = 998244353;
  const long long MOD2 = 2010405347;
  const long long INF = 2e18;
  const int dr[] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
  const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1, 0};
  const double pi = acos(-1);
  const double EPS = 1e-9;
  const int block = 315;
  inline long long pw(long long x, long long y, long long md = MOD) {
    long long ret = 1;
    x %= md;
    while (y) {
      if (y & 1) ret = ret * x % md;
      x = x * x % md, y >>= 1;
    }
    return ret;
  }
  inline void add(int &a, int b, int md = MOD) {
    a = a + b >= md ? a + b - md : a + b;
  }
  int n, m, k, le[MAX], ri[MAX], x[MAX], c, cnt[MAX], nx[MAX], ls[MAX], hit, nw,
      p[MAX], a, b;
  bool st[MAX], tmp;
  long long ans, dp[MAX];
  vector<pair<int, int> > v;
  long long f(int rem) {
    if (!rem) return 1;
    if (dp[rem] != -1) return dp[rem];
    long long ret = 0;
    for (pair<int, int> &i : v) {
      if (i.first > rem) break;
      ret += f(rem - i.first) * i.second;
    }
    return dp[rem] = ret % MOD;
  }
  int par(int z) {
    if (p[z] == z) return z;
    return p[z] = par(p[z]);
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> c;
    for (int i = (1); i <= (c); ++i) p[i] = i, st[i] = 1;
    for (int i = (1); i <= (n); ++i) {
      cin >> k;
      for (int i = (1); i <= (k); ++i) cin >> x[i];
      tmp = 1;
      for (int i = (2); i <= (k); ++i) {
        if ((nx[x[i - 1]] && nx[x[i - 1]] != x[i]) ||
            (ls[x[i]] && ls[x[i]] != x[i - 1]) || x[i] == x[i - 1])
          tmp = 0;
        a = par(x[i - 1]), b = par(x[i]);
        tmp &= st[a] && st[b];
        p[b] = a;
        st[a] = tmp;
        if (!tmp) continue;
        nx[x[i - 1]] = x[i];
        ls[x[i]] = x[i - 1];
      }
    }
    for (int i = (1); i <= (c); ++i)
      if (!ls[i] && st[par(i)]) {
        if (!nx[i])
          ++cnt[1];
        else {
          nw = i, hit = 1;
          while (nx[nw]) nw = nx[nw], ++hit;
          ++cnt[hit];
        }
      }
    for (int i = (1); i <= (m); ++i)
      if (cnt[i]) v.push_back({i, cnt[i]});
    memset(&dp, -1, sizeof dp);
    cout << f(m) << '\n';
    return 0;
  }
  