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 MAXN = 3e5 + 5;
  const int MAXM = 3e5 + 5;
  const int MAXD = 3e5 + 5;
  const int mod = 998244353;
  inline void add_mod(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
  }
  bool fob[MAXD];
  vector<int> lef[MAXD], rig[MAXD];
  inline void sort_unique(vector<int> &vec) {
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
  }
  void dfs_fob(int u) {
    if (fob[u]) return;
    fob[u] = 1;
    for (int x : lef[u]) dfs_fob(x);
    for (int x : rig[u]) dfs_fob(x);
  }
  int main(void) {
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= n; ++i) {
      int k;
      scanf("%d", &k);
      vector<int> vec(k);
      for (int &x : vec) scanf("%d", &x);
      for (int j = 1; j < k; ++j) {
        lef[vec[j]].push_back(vec[j - 1]);
        rig[vec[j - 1]].push_back(vec[j]);
      }
    }
    for (int i = 1; i <= d; ++i) {
      sort_unique(lef[i]);
      sort_unique(rig[i]);
      if (lef[i].size() > 1 || rig[i].size() > 1) dfs_fob(i);
    }
    static bool vis[MAXD];
    map<int, int> tlens;
    for (int i = 1; i <= d; ++i)
      if (!vis[i] && !lef[i].size() && !fob[i]) {
        int cur = 0, u = i;
        while (1) {
          if (vis[u]) {
            dfs_fob(u);
            break;
          }
          ++cur;
          vis[u] = 1;
          if (rig[u].size())
            u = rig[u][0];
          else
            break;
        }
        if (!fob[i]) ++tlens[cur];
      }
    vector<pair<int, int> > lens(tlens.begin(), tlens.end());
    static int f[MAXM];
    f[0] = 1;
    for (int i = 1; i <= m; ++i)
      for (pair<int, int> &x : lens) {
        if (x.first > i) break;
        f[i] = (f[i] + (long long)f[i - x.first] * x.second) % mod;
      }
    printf("%d", f[m]);
    return 0;
  }
  