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;
  template <typename T>
  void read(T &x) {
    x = 0;
    int op = 1;
    char c = getchar();
    while (!isdigit(c)) {
      if (c == '-') op = -1;
      c = getchar();
    }
    while (isdigit(c)) {
      x = (x << 1) + (x << 3) + (c ^ 48);
      c = getchar();
    }
    x *= op;
  }
  inline void swap(int &x, int &y) { x ^= y ^= x ^= y; }
  inline int min(int x, int y) { return x < y ? x : y; }
  inline int max(int x, int y) { return x > y ? x : y; }
  const int Mod = 998244353;
  int Pls(int x, int y) {
    x += y;
    return x >= Mod ? x - Mod : x;
  }
  const int MN = 300000 + 10;
  int N, M, K;
  vector<int> pre[MN], nxt[MN];
  bool fob[MN], vis[MN];
  int cnt[MN];
  vector<pair<int, int> > len;
  int dp[MN];
  void Adde(int x, int y) {
    pre[y].push_back(x);
    nxt[x].push_back(y);
  }
  void DFS(int x) {
    if (fob[x]) return;
    fob[x] = 1;
    for (int y : pre[x]) DFS(y);
    for (int y : nxt[x]) DFS(y);
  }
  int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; ++i) {
      int c;
      scanf("%d", &c);
      vector<int> A(c);
      for (int &x : A) scanf("%d", &x);
      for (int j = 1; j < c; ++j) Adde(A[j - 1], A[j]);
    }
    for (int i = 1; i <= K; ++i) {
      sort((pre[i]).begin(), (pre[i]).end());
      pre[i].erase(unique((pre[i]).begin(), (pre[i]).end()), pre[i].end());
      sort((nxt[i]).begin(), (nxt[i]).end());
      nxt[i].erase(unique((nxt[i]).begin(), (nxt[i]).end()), nxt[i].end());
      if ((int)(pre[i]).size() > 1 || (int)(nxt[i]).size() > 1) DFS(i);
    }
    for (int i = 1; i <= K; ++i)
      if (!fob[i] && !(int)(pre[i]).size()) {
        int l = 0, x = i;
        while (1) {
          if (vis[x]) {
            DFS(x);
            break;
          }
          vis[x] = 1;
          l++;
          if ((int)(nxt[x]).size())
            x = nxt[x][0];
          else
            break;
        }
        cnt[l]++;
      }
    for (int i = 1; i <= K; ++i)
      if (cnt[i]) len.push_back(make_pair(i, cnt[i]));
    dp[0] = 1;
    for (int i = 1; i <= M; ++i)
      for (pair<int, int> j : len)
        if (j.first <= i)
          dp[i] = Pls(dp[i], 1ll * dp[i - j.first] * j.second % Mod);
    printf("%d\n", dp[M]);
    return 0;
  }
  