#include <bits/stdc++.h>
template <class p, class q>
void umin(p& a, const q& b) {
  if (a > b) a = b;
}
template <class p, class q>
void umax(p& a, const q& b) {
  if (a < b) a = b;
}
using ll = long long;
using VI = std::vector<int>;
using namespace std;
using namespace std::chrono;
int n, m, k;
int const N = 3e5 + 3;
ll const P = 998244353;
ll const gen = 906409729;
ll const invgen = 483587622;
ll root[21];
ll invroot[21];
ll inv[3] = {0, 1, (P + 1) / 2};
void calc() {
  root[20] = gen;
  invroot[20] = invgen;
  for (int i = (19); i >= (0); i--) root[i] = (root[i + 1] * root[i + 1]) % P;
  for (int i = (19); i >= (0); i--)
    invroot[i] = (invroot[i + 1] * invroot[i + 1]) % P;
}
void fft(vector<ll>& b, bool invert) {
  int m = b.size();
  if (m == 1) return;
  vector<ll> b0, b1;
  for (int i = 0; 2 * i < m; i++) {
    b0.push_back(b[2 * i]);
    b1.push_back(b[2 * i + 1]);
  }
  fft(b0, invert);
  fft(b1, invert);
  ll w = 1;
  ll wn = (invert) ? invroot[(int)(log2)(m)] : root[(int)(log2)(m)];
  for (int i = 0; 2 * i < m; i++) {
    b[i] = (b0[i] + w * b1[i]) % P;
    b[i + m / 2] = ((b0[i] - w * b1[i]) % P + P) % P;
    w = (w * wn) % P;
    if (invert) {
      b[i] = (b[i] * inv[2]) % P;
      b[i + m / 2] = (b[i + m / 2] * inv[2]) % P;
    }
  }
}
void inverse(vector<ll>& ret, vector<ll> first, int r) {
  assert(r > 0);
  assert(first[0] == 1);
  if (r == 1) {
    ret = vector<ll>{1};
  } else {
    first.resize(r);
    vector<ll> halfinverse;
    inverse(halfinverse, first, r / 2);
    int s = 2 * r;
    first.resize(s);
    halfinverse.resize(s);
    fft(first, 0);
    fft(halfinverse, 0);
    ret = vector<ll>(s);
    for (int i = (0); i <= (s - 1); i++)
      ret[i] = (2 + P - (first[i] * halfinverse[i]) % P) % P;
    for (int i = (0); i <= (s - 1); i++) ret[i] = (halfinverse[i] * ret[i]) % P;
    fft(ret, 1);
    ret.resize(r);
  }
}
vector<VI> arrays;
VI D[N];
VI Din[N];
vector<ll> W;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  arrays = vector<VI>(n);
  for (int i = (1); i <= (n); i++) {
    int t;
    cin >> t;
    for (int j = (1); j <= (t); j++) {
      int s;
      cin >> s;
      arrays[i - 1].push_back(s);
    }
    for (int j = (0); j <= (t - 2); j++) {
      D[arrays[i - 1][j]].push_back(arrays[i - 1][j + 1]);
      Din[arrays[i - 1][j + 1]].push_back(arrays[i - 1][j]);
    }
  }
  for (int i = (1); i <= (k); i++) {
    sort(D[i].begin(), D[i].end());
    sort(Din[i].begin(), Din[i].end());
    D[i].erase(unique(D[i].begin(), D[i].end()), D[i].end());
    Din[i].erase(unique(Din[i].begin(), Din[i].end()), Din[i].end());
  }
  W = vector<ll>(m + 1);
  bool out = 1;
  for (int i = (1); i <= (k); i++) {
    if (Din[i].empty()) {
      int ww = 1;
      int ci = i;
      while (1) {
        if (((int)((D[ci]).size())) > 1 || ((int)((Din[ci]).size())) > 1)
          break;
        else if (((int)((D[ci]).size())) == 1) {
          ww++;
          ci = D[ci][0];
        } else {
          out = 0;
          if (ww <= m) W[ww]--;
          break;
        }
      }
    }
  }
  if (out) {
    cout << "0\n";
    return 0;
  }
  W[0] = 1;
  calc();
  vector<ll> ans;
  int pot2 = 1;
  while (pot2 <= m) pot2 *= 2;
  inverse(ans, W, pot2);
  if (((int)((ans).size())) > m)
    cout << ans[m] << "\n";
  else
    cout << "0\n";
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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

### Response

```cpp
#include <bits/stdc++.h>
template <class p, class q>
void umin(p& a, const q& b) {
  if (a > b) a = b;
}
template <class p, class q>
void umax(p& a, const q& b) {
  if (a < b) a = b;
}
using ll = long long;
using VI = std::vector<int>;
using namespace std;
using namespace std::chrono;
int n, m, k;
int const N = 3e5 + 3;
ll const P = 998244353;
ll const gen = 906409729;
ll const invgen = 483587622;
ll root[21];
ll invroot[21];
ll inv[3] = {0, 1, (P + 1) / 2};
void calc() {
  root[20] = gen;
  invroot[20] = invgen;
  for (int i = (19); i >= (0); i--) root[i] = (root[i + 1] * root[i + 1]) % P;
  for (int i = (19); i >= (0); i--)
    invroot[i] = (invroot[i + 1] * invroot[i + 1]) % P;
}
void fft(vector<ll>& b, bool invert) {
  int m = b.size();
  if (m == 1) return;
  vector<ll> b0, b1;
  for (int i = 0; 2 * i < m; i++) {
    b0.push_back(b[2 * i]);
    b1.push_back(b[2 * i + 1]);
  }
  fft(b0, invert);
  fft(b1, invert);
  ll w = 1;
  ll wn = (invert) ? invroot[(int)(log2)(m)] : root[(int)(log2)(m)];
  for (int i = 0; 2 * i < m; i++) {
    b[i] = (b0[i] + w * b1[i]) % P;
    b[i + m / 2] = ((b0[i] - w * b1[i]) % P + P) % P;
    w = (w * wn) % P;
    if (invert) {
      b[i] = (b[i] * inv[2]) % P;
      b[i + m / 2] = (b[i + m / 2] * inv[2]) % P;
    }
  }
}
void inverse(vector<ll>& ret, vector<ll> first, int r) {
  assert(r > 0);
  assert(first[0] == 1);
  if (r == 1) {
    ret = vector<ll>{1};
  } else {
    first.resize(r);
    vector<ll> halfinverse;
    inverse(halfinverse, first, r / 2);
    int s = 2 * r;
    first.resize(s);
    halfinverse.resize(s);
    fft(first, 0);
    fft(halfinverse, 0);
    ret = vector<ll>(s);
    for (int i = (0); i <= (s - 1); i++)
      ret[i] = (2 + P - (first[i] * halfinverse[i]) % P) % P;
    for (int i = (0); i <= (s - 1); i++) ret[i] = (halfinverse[i] * ret[i]) % P;
    fft(ret, 1);
    ret.resize(r);
  }
}
vector<VI> arrays;
VI D[N];
VI Din[N];
vector<ll> W;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  arrays = vector<VI>(n);
  for (int i = (1); i <= (n); i++) {
    int t;
    cin >> t;
    for (int j = (1); j <= (t); j++) {
      int s;
      cin >> s;
      arrays[i - 1].push_back(s);
    }
    for (int j = (0); j <= (t - 2); j++) {
      D[arrays[i - 1][j]].push_back(arrays[i - 1][j + 1]);
      Din[arrays[i - 1][j + 1]].push_back(arrays[i - 1][j]);
    }
  }
  for (int i = (1); i <= (k); i++) {
    sort(D[i].begin(), D[i].end());
    sort(Din[i].begin(), Din[i].end());
    D[i].erase(unique(D[i].begin(), D[i].end()), D[i].end());
    Din[i].erase(unique(Din[i].begin(), Din[i].end()), Din[i].end());
  }
  W = vector<ll>(m + 1);
  bool out = 1;
  for (int i = (1); i <= (k); i++) {
    if (Din[i].empty()) {
      int ww = 1;
      int ci = i;
      while (1) {
        if (((int)((D[ci]).size())) > 1 || ((int)((Din[ci]).size())) > 1)
          break;
        else if (((int)((D[ci]).size())) == 1) {
          ww++;
          ci = D[ci][0];
        } else {
          out = 0;
          if (ww <= m) W[ww]--;
          break;
        }
      }
    }
  }
  if (out) {
    cout << "0\n";
    return 0;
  }
  W[0] = 1;
  calc();
  vector<ll> ans;
  int pot2 = 1;
  while (pot2 <= m) pot2 *= 2;
  inverse(ans, W, pot2);
  if (((int)((ans).size())) > m)
    cout << ans[m] << "\n";
  else
    cout << "0\n";
  return 0;
}

```