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 = 1e6 + 10;
  const long long mod = 998244353;
  inline long long gcd(long long a, long long b) {
    return !b ? a : gcd(b, a % b);
  }
  inline long long q_pow(long long a, long long x = mod - 2) {
    long long ans = 1, tmp = a;
    while (x) {
      if (x & 1) (ans *= tmp) %= mod;
      (tmp *= tmp) %= mod;
      x >>= 1;
    }
    return ans;
  }
  template <typename T>
  inline void re(T &N) {
    int f = 1;
    char c;
    while ((c = getchar()) < '0' || c > '9')
      if (c == '-') f = -1;
    N = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') N = N * 10 + c - '0';
    N *= f;
  }
  template <class T, class... T_>
  inline void re(T &x, T_ &...y) {
    re(x), re(y...);
  }
  int m, n, k, t = 1, st, en;
  int vis[N];
  int cnt[N];
  long long dp[N];
  vector<int> in[N], out[N];
  inline void add(int x, int y) {
    in[y].push_back(x);
    out[x].push_back(y);
  }
  int bad[N];
  void expand(int x) {
    if (bad[x]) return;
    bad[x] = 1;
    for (int i : in[x]) expand(i);
    for (int i : out[x]) expand(i);
  }
  vector<int> v[N];
  int main() {
    re(n, m, k);
    for (int i = 1; i <= n; i++) {
      int len;
      re(len);
      v[i] = vector<int>(len);
      for (int j = 0; j < len; j++) re(v[i][j]);
      for (int j = 0; j + 1 < len; j++) add(v[i][j], v[i][j + 1]);
    }
    for (int i = 1; i <= n; i++) {
      if (set<int>(v[i].begin(), v[i].end()).size() != v[i].size())
        for (int j : v[i]) expand(j);
    }
    for (int i = 1; i <= k; i++) {
      sort(in[i].begin(), in[i].end());
      in[i].erase(unique(in[i].begin(), in[i].end()), in[i].end());
      sort(out[i].begin(), out[i].end());
      out[i].erase(unique(out[i].begin(), out[i].end()), out[i].end());
    }
    for (int i = 1; i <= k; i++) {
      if (bad[i]) continue;
      if (in[i].size() > 1 || out[i].size() > 1) {
        expand(i);
        continue;
      }
      if (vis[i]) continue;
      queue<int> q;
      q.push(i);
      vis[i] = 1;
      int ok = 1;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int j : out[x]) {
          if (vis[j]) {
            ok = 0;
            break;
          }
          vis[j] = 1;
          q.push(j);
        }
        if (!ok) {
          expand(x);
          break;
        }
      }
      if (ok) {
        q.push(i);
        while (!q.empty()) {
          int x = q.front();
          q.pop();
          for (int j : in[x]) {
            if (vis[j]) continue;
            vis[j] = 1;
            q.push(j);
          }
        }
      }
    }
    fill(vis + 1, vis + k + 1, 0);
    for (int i = 1; i <= k; i++)
      if (!bad[i] && !vis[i]) {
        int sum = 1;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        while (!q.empty()) {
          int x = q.front();
          q.pop();
          for (int j : in[x]) {
            if (vis[j]) continue;
            sum++;
            vis[j] = 1;
            q.push(j);
          }
          for (int j : out[x]) {
            if (vis[j]) continue;
            sum++;
            vis[j] = 1;
            q.push(j);
          }
        }
        cnt[sum]++;
      }
    vector<int> key;
    for (int i = 1; i <= m; i++)
      if (cnt[i]) key.push_back(i);
    dp[0] = 1;
    for (int i = 1; i <= m; i++)
      for (int j : key)
        if (i >= j) (dp[i] += dp[i - j] * cnt[j] % mod) %= mod;
    printf("%lld\n", dp[m]);
  }
  