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>
  using namespace std;
  const int N = 3e5 + 5;
  const long long mod = 998244353;
  int n, m, k;
  int Pre[N], Suc[N];
  int cnt[N], nxt[N];
  bool CanId[N], CanVec[N], tVis[N];
  long long dp[N << 1];
  vector<int> vec[N], Sons[N];
  int fa[N];
  int _Find(int u) { return u == fa[u] ? u : fa[u] = _Find(fa[u]); }
  void check(int Col) {
    for (int now = Suc[Col]; now; now = Suc[now]) {
      int fu = _Find(Pre[now]), fv = _Find(now);
      if (fu == fv)
        CanId[Pre[now]] = CanId[now] = 0;
      else
        fa[fu] = fv;
    }
  }
  bool CheckCircle(int Col) {
    if (tVis[Col]) return 1;
    for (int now = Suc[Col]; now; now = Suc[now])
      if (Col == now)
        return 0;
      else
        tVis[now] = 1;
    return 1;
  }
  bool CheckVec(int Id) {
    bool ret = 1;
    for (int i = 0; i < vec[Id].size(); i++)
      if (tVis[vec[Id][i]]) {
        ret = 0;
        break;
      } else
        tVis[vec[Id][i]] = 1;
    for (int i = 0; i < vec[Id].size(); i++) tVis[vec[Id][i]] = 0;
    if (!ret) CanId[vec[Id][0]] = 0;
    return ret;
  }
  int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++) fa[i] = i, CanId[i] = CanVec[i] = 1;
    for (int C, i = 1; i <= n; i++) {
      scanf("%d", &C);
      for (int x; C--;) scanf("%d", &x), vec[i].push_back(x);
      CheckVec(i);
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j < vec[i].size(); j++) {
        int Up = vec[i][j - 1], Down = vec[i][j];
        if ((!Pre[Down] || Pre[Down] == Up) && (!Suc[Up] || Suc[Up] == Down)) {
          Pre[Down] = Up;
          Suc[Up] = Down;
        } else
          CanId[Up] = CanId[Down] = 0;
      }
    }
    for (int i = 1; i <= k; i++)
      if (!Pre[i]) check(i);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j < vec[i].size(); j++) {
        int Up = vec[i][j - 1], Down = vec[i][j];
        int fu = _Find(Up), fv = _Find(Down);
        if (fu != fv) fa[fu] = fv;
      }
    for (int i = 1; i <= k; i++) _Find(i);
    for (int i = 1; i <= k; i++) tVis[i] = 0;
    for (int i = 1; i <= k; i++) Sons[fa[i]].push_back(i);
    for (int i = 1; i <= k; i++)
      if (!CheckCircle(i)) CanId[i] = 0;
    for (int i = 1; i <= k; i++)
      if (!CanId[i]) CanVec[fa[i]] = 0;
    for (int i = 1; i <= k; i++)
      if (CanVec[i] && Sons[i].size() > 0U) cnt[Sons[i].size()]++;
    int tHead = 0;
    for (int i = 1; i <= k; i++) {
      if (cnt[i]) nxt[tHead] = i, tHead = i;
    }
    dp[0] = 1;
    for (int i = 0; i <= m; i++) {
      for (int j = nxt[0]; j; j = nxt[j]) {
        (dp[i + j] += dp[i] * cnt[j]) %= mod;
      }
    }
    printf("%lld\n", dp[m]);
    return 0;
  }
  