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 <long long mod>
  struct modular {
    long long value;
    modular(long long x = 0) {
      value = x % mod;
      if (value < 0) value += mod;
    }
    modular& operator+=(const modular& other) {
      if ((value += other.value) >= mod) value -= mod;
      return *this;
    }
    modular& operator-=(const modular& other) {
      if ((value -= other.value) < 0) value += mod;
      return *this;
    }
    modular& operator*=(const modular& other) {
      value = value * other.value % mod;
      return *this;
    }
    modular& operator/=(const modular& other) {
      long long a = 0, b = 1, c = other.value, m = mod;
      while (c != 0) {
        long long t = m / c;
        m -= t * c;
        swap(c, m);
        a -= t * b;
        swap(a, b);
      }
      a %= mod;
      if (a < 0) a += mod;
      value = value * a % mod;
      return *this;
    }
    modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
    modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
    modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
    modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
    modular& operator++() { return *this += 1; }
    modular& operator--() { return *this -= 1; }
    modular operator++(int) {
      modular res(*this);
      *this += 1;
      return res;
    }
    modular operator--(int) {
      modular res(*this);
      *this -= 1;
      return res;
    }
    modular operator-() const { return modular(-value); }
    bool operator==(const modular& rhs) const { return value == rhs.value; }
    bool operator!=(const modular& rhs) const { return value != rhs.value; }
    bool operator<(const modular& rhs) const { return value < rhs.value; }
  };
  template <long long mod>
  string to_string(const modular<mod>& x) {
    return to_string(x.value);
  }
  template <long long mod>
  ostream& operator<<(ostream& stream, const modular<mod>& x) {
    return stream << x.value;
  }
  template <long long mod>
  istream& operator>>(istream& stream, modular<mod>& x) {
    stream >> x.value;
    x.value %= mod;
    if (x.value < 0) x.value += mod;
    return stream;
  }
  constexpr long long mod = 998244353;
  using mint = modular<mod>;
  mint power(mint a, long long n) {
    mint res = 1;
    while (n > 0) {
      if (n & 1) {
        res *= a;
      }
      a *= a;
      n >>= 1;
    }
    return res;
  }
  vector<mint> fact(1, 1);
  vector<mint> finv(1, 1);
  mint C(int n, int k) {
    if (n < k || k < 0) {
      return mint(0);
    }
    while ((int)fact.size() < n + 1) {
      fact.emplace_back(fact.back() * (int)fact.size());
      finv.emplace_back(mint(1) / fact.back());
    }
    return fact[n] * finv[k] * finv[n - k];
  }
  struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;
    dsu(int _n) : n(_n) {
      p.resize(n);
      iota(p.begin(), p.end(), 0);
      sz.assign(n, 1);
    }
    inline int get(int x) {
      if (p[x] == x) {
        return x;
      } else {
        return p[x] = get(p[x]);
      }
    }
    inline bool unite(int x, int y) {
      x = get(x);
      y = get(y);
      if (x == y) {
        return false;
      }
      if (sz[x] > sz[y]) {
        swap(x, y);
      }
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    inline bool same(int x, int y) { return (get(x) == get(y)); }
  };
  mint root;
  int base;
  int max_base;
  vector<mint> roots;
  vector<int> rev;
  void ensure_base(int nbase) {
    if (roots.empty()) {
      auto tmp = mod - 1;
      max_base = 0;
      while (tmp % 2 == 0) {
        tmp /= 2;
        max_base++;
      }
      root = 2;
      while (power(root, (mod - 1) >> 1) == 1) {
        root += 1;
      }
      root = power(root, (mod - 1) >> max_base);
      base = 1;
      rev = {0, 1};
      roots = {0, 1};
    }
    if (nbase <= base) {
      return;
    }
    rev.resize(1 << nbase);
    for (int i = 0; i < (1 << nbase); i++) {
      rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
    }
    roots.resize(1 << nbase);
    while (base < nbase) {
      mint z = power(root, 1 << (max_base - 1 - base));
      for (int i = 1 << (base - 1); i < (1 << base); i++) {
        roots[i << 1] = roots[i];
        roots[(i << 1) + 1] = roots[i] * z;
      }
      base++;
    }
  }
  void ntt(vector<mint>& a) {
    int n = (int)a.size();
    int zeros = __builtin_ctz(n);
    ensure_base(zeros);
    int shift = base - zeros;
    for (int i = 0; i < n; i++) {
      if (i < (rev[i] >> shift)) {
        swap(a[i], a[rev[i] >> shift]);
      }
    }
    for (int k = 1; k < n; k <<= 1) {
      for (int i = 0; i < n; i += 2 * k) {
        for (int j = 0; j < k; j++) {
          mint x = a[i + j];
          mint y = a[i + j + k] * roots[j + k];
          a[i + j] = x + y;
          a[i + j + k] = x - y;
        }
      }
    }
  }
  vector<mint> multiply(vector<mint> a, vector<mint> b) {
    int need = (int)a.size() + (int)b.size() - 1;
    int nbase = 0;
    while ((1 << nbase) < need) {
      nbase++;
    }
    ensure_base(nbase);
    int sz = 1 << nbase;
    a.resize(sz);
    b.resize(sz);
    ntt(a);
    ntt(b);
    mint inv = mint(1) / mint(sz);
    for (int i = 0; i < sz; i++) {
      a[i] *= b[i] * inv;
    }
    reverse(a.begin() + 1, a.end());
    ntt(a);
    a.resize(need);
    return a;
  }
  vector<mint>& operator*=(vector<mint>& a, const vector<mint>& b) {
    if (min(a.size(), b.size()) < 150) {
      vector<mint> c = a;
      a.assign(a.size() + b.size() - 1, 0);
      for (int i = 0; i < (int)c.size(); i++) {
        for (int j = 0; j < (int)b.size(); j++) {
          a[i + j] += c[i] * b[j];
        }
      }
    } else {
      a = multiply(a, b);
    }
    return a;
  }
  template <typename T>
  vector<T> operator*(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c *= b;
  }
  template <typename T>
  vector<T> inverse(const vector<T>& a) {
    vector<T> h(a);
    int n = (int)h.size();
    T invh0 = T(1) / h[0];
    vector<T> u(1, invh0);
    while ((int)u.size() < n) {
      int t = (int)u.size();
      vector<T> h0;
      for (int i = 0; i < t; i++) {
        h0.emplace_back(i < (int)h.size() ? h[i] : 0);
      }
      vector<T> c = h0 * u;
      vector<T> h1;
      for (int i = t; i < 2 * t; i++) {
        h1.emplace_back(i < (int)h.size() ? h[i] : 0);
      }
      vector<T> aux = u * h1;
      aux.resize(t);
      for (int i = 0; i < t; i++) {
        aux[i] += (i + t < (int)c.size() ? c[i + t] : 0);
      }
      vector<T> v = aux * u;
      v.resize(t);
      for (int i = 0; i < t; i++) {
        u.emplace_back(-v[i]);
      }
    }
    u.resize(n);
    return u;
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a;
    for (int i = 0; i < n; i++) {
      int c;
      cin >> c;
      vector<int> b(c);
      for (int j = 0; j < c; j++) {
        cin >> b[j];
        b[j]--;
      }
      a.emplace_back(b);
    }
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    n = (int)a.size();
    vector<int> nxt(k, -1), pre(k, 0);
    dsu uf(k + 1);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < (int)a[i].size() - 1; j++) {
        uf.unite(a[i][j], a[i][j + 1]);
        if (nxt[a[i][j]] != a[i][j + 1]) {
          if (nxt[a[i][j]] == -1) {
            nxt[a[i][j]] = a[i][j + 1];
            pre[a[i][j + 1]]++;
          } else {
            uf.unite(a[i][j], k);
          }
        }
      }
    }
    vector<mint> b(m + 1);
    for (int i = 0; i < k; i++) {
      if (uf.same(i, k) || pre[i]) {
        continue;
      }
      vector<int> c;
      c.emplace_back(i);
      int now = i;
      while (nxt[now] != -1) {
        c.emplace_back(nxt[now]);
        now = nxt[now];
        if (pre[now] != 1) {
          c.clear();
          break;
        }
      }
      if ((int)c.size() == uf.sz[uf.get(i)] && (int)c.size() <= m) {
        b[c.size()]++;
      } else {
        uf.unite(i, k);
      }
    };
    vector<mint> c(m + 1);
    c[0] = 1;
    for (int i = 1; i <= m; i++) {
      c[i] = -b[i];
    }
    c = inverse(c);
    b *= c;
    cout << b[m] << '\n';
    return 0;
  }
  