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;
  vector<long long> a[300010];
  long long pre[300010], nxt[300010];
  bool vis[300010];
  vector<long long> pack;
  const long long mod = 998244353;
  inline long long fastpow(long long a, long long n) {
    long long ans = 1;
    while (n) {
      if (n & 1) ans = ans * a % mod;
      a = a * a % mod;
      n >>= 1;
    }
    return ans;
  }
  inline long long inv(long long x) { return fastpow(x, mod - 2); }
  const long long g = 3, ig = inv(g);
  long long r[2000000];
  inline void getr(long long lim, long long n) {
    for (long long i = 0; i < lim; i++)
      r[i] = (r[i >> 1] >> 1) | ((i & 1) << (n - 1));
  }
  inline void NTT(long long *a, long long n, long long op) {
    for (long long i = 0; i < n; i++)
      if (i < r[i]) swap(a[i], a[r[i]]);
    for (long long i = 1; i < n; i <<= 1) {
      long long wn = fastpow(op == 1 ? g : ig, (mod - 1) / (i << 1));
      for (long long j = 0; j < n; j += (i << 1)) {
        long long w = 1;
        for (long long k = 0; k < i; k++, w = w * wn % mod) {
          long long x = a[j + k], y = w * a[j + k + i] % mod;
          a[j + k] = (x + y) % mod;
          a[j + k + i] = (x - y + mod) % mod;
        }
      }
    }
    if (op == -1) {
      long long il = inv(n);
      for (long long i = 0; i < n; i++) a[i] = a[i] * il % mod;
    }
  }
  long long A[2000000], B[2000000];
  void work(long long *a, long long *b, long long n, long long cnt) {
    static long long tmp[2000000];
    if (n == 1) {
      b[0] = inv(a[0]);
      return;
    }
    work(a, b, n >> 1, cnt - 1);
    long long lim = n << 1;
    for (long long i = 0; i < n; i++) tmp[i] = a[i];
    for (long long i = n; i < lim; i++) tmp[i] = 0;
    getr(lim, cnt + 1);
    NTT(tmp, lim, 1);
    NTT(b, lim, 1);
    for (long long i = 0; i < lim; i++)
      b[i] = b[i] * (2 - tmp[i] * b[i] % mod + mod) % mod;
    NTT(b, lim, -1);
    for (long long i = n; i < lim; i++) b[i] = 0;
  }
  signed main() {
    long long n, m, k;
    scanf("%lld %lld %lld", &n, &m, &k);
    for (long long i = 1; i <= n; i++) {
      long long t;
      scanf("%lld", &t);
      while (t--) {
        long long x;
        scanf("%lld", &x);
        a[i].push_back(x);
      }
    }
    for (long long i = 1; i <= n; i++) {
      long long len = a[i].size();
      for (long long j = 0; j < len; j++) {
        if (j != 0) {
          if (pre[a[i][j]] != 0 && pre[a[i][j]] != a[i][j - 1])
            pre[a[i][j]] = -1;
          else
            pre[a[i][j]] = a[i][j - 1];
        }
        if (j != len - 1) {
          if (nxt[a[i][j]] != 0 && nxt[a[i][j]] != a[i][j + 1])
            nxt[a[i][j]] = -1;
          else
            nxt[a[i][j]] = a[i][j + 1];
        }
      }
    }
    for (long long i = 1; i <= k; i++)
      if (!pre[i] && !vis[i]) {
        long long tot = 0, u = i;
        bool flag = true;
        while (u) {
          tot++;
          if (vis[u] || pre[u] == -1 || nxt[u] == -1) {
            flag = false;
            break;
          }
          vis[u] = true;
          u = nxt[u];
        }
        if (flag) pack.push_back(tot);
      }
    A[0] = mod - 1;
    for (auto x : pack) A[x]++;
    long long lim = 1, cnt = 0;
    while (lim <= max(k, m)) lim <<= 1, cnt++;
    work(A, B, lim, cnt);
    printf("%lld\n", (mod - B[m]) % mod);
    return 0;
  }
  