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 double PI = acos(-1);
  #pragma GCC optimize("Ofast")
  #pragma GCC optimize("O2")
  #pragma GCC optimize("O3")
  #pragma GCC optimize("unroll-loops")
  #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  const int MOD = 998244353;
  const int MAXN = 3e5 + 100;
  const int LOGN = 20;
  void clear() {}
  void precalc() {}
  void gen_tests() {}
  int sum(int a, int b) { return (a + b) % MOD; }
  int mult(int a, int b) { return ((long long)a * b) % MOD; }
  set<int> added_indexes[MAXN];
  struct Number {
    map<int, int> numbers;
    map<int, int> back_numbers;
    int delta = 0;
    int index;
    int Get(int ind) { return numbers[ind - delta]; }
    void Set(int ind, int val) {
      numbers[ind - delta] = val;
      back_numbers[val] = ind - delta;
    }
    int Size() { return numbers.size(); }
    int GetIndex(int value) { return back_numbers[value] + delta; }
    bool TryMerge(Number &number) {
      if (back_numbers.count(number.Get(0))) {
        int s_index = GetIndex(number.Get(0));
        int common_elements = 0;
        for (int i = 0; i + s_index < Size() && i < number.Size(); i++) {
          if (Get(i + s_index) != number.Get(i)) return false;
          common_elements++;
        }
        for (int i = common_elements; i < number.Size(); i++) {
          int val = number.Get(i);
          added_indexes[val].insert(index);
          Set(s_index + i, val);
        }
        return numbers.size() == back_numbers.size();
      } else if (number.back_numbers.count(Get(0))) {
        int s_index = number.GetIndex(Get(0));
        for (int i = 0; i < Size() && i + s_index < number.Size(); i++) {
          if (Get(i) != number.Get(i + s_index)) return false;
        }
        delta += s_index;
        for (int i = 0; i < s_index; i++) {
          int val = number.Get(i);
          added_indexes[val].insert(index);
          Set(i, val);
        }
        return numbers.size() == back_numbers.size();
      }
      return false;
    }
  };
  Number numbers[MAXN];
  bool is_free[MAXN];
  bool added[MAXN];
  void FullRemove(int index, bool add_more) {
    queue<int> q;
    q.push(index);
    added[index] = false;
    while (!q.empty()) {
      auto top = q.front();
      q.pop();
      for (auto u : numbers[top].back_numbers) {
        int val = u.first;
        added_indexes[val].erase(top);
        for (auto v : added_indexes[val]) {
          if (added[v] && add_more) {
            added[v] = false;
            q.push(v);
          }
        }
      }
    }
  }
  int results[MAXN];
  void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
      numbers[i].index = i;
      added[i] = 1;
      int c;
      cin >> c;
      bool must_remove = false;
      for (int j = 0; j < c; j++) {
        int val;
        cin >> val;
        numbers[i].Set(j, val);
        if (is_free[val] && added_indexes[val].size() == 0) must_remove = true;
        added_indexes[val].insert(i);
        is_free[val] = true;
      }
      must_remove |= numbers[i].back_numbers.size() != numbers[i].numbers.size();
      if (must_remove) {
        FullRemove(i, true);
        continue;
      }
      int v = i;
      set<int> merge_queue;
      for (auto u : numbers[i].back_numbers) {
        for (auto m : added_indexes[u.first]) {
          if (m != i) merge_queue.insert(m);
        }
      }
      for (int to : merge_queue) {
        if (numbers[v].Size() < numbers[to].Size()) {
          swap(v, to);
        }
        must_remove = !numbers[v].TryMerge(numbers[to]);
        if (must_remove) break;
        FullRemove(to, false);
      }
      if (must_remove) FullRemove(v, true);
    }
    map<int, int> shifts;
    for (int i = 1; i <= k; i++) {
      if (!is_free[i]) shifts[1]++;
    }
    for (int i = 0; i < n; i++) {
      if (added[i]) {
        shifts[numbers[i].Size()]++;
      }
    }
    vector<pair<int, int> > moves;
    for (auto u : shifts) {
      moves.push_back({u.first, u.second});
    }
    results[0] = 1;
    for (int i = 0; i < m; i++) {
      for (auto u : moves) {
        if (i + u.first > m) break;
        results[i + u.first] =
            sum(results[i + u.first], mult(u.second, results[i]));
      }
    }
    cout << results[m];
  }
  void multisolve() {
    int t;
    cin >> t;
    while (t--) {
      solve();
    }
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    precalc();
    solve();
    return 0;
  }
  