#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const unsigned long long p = 19260817;
inline int read(int x = 0, char c = getchar(), bool f = 0) {
  while (c < '0' || c > '9') f = c == '-', c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
  return f ? -x : x;
}
int n, m, k;
int c[300050], dp[300050], al[300050];
vector<int> v[300050];
vector<unsigned long long> hs[300050];
unsigned long long po[300050];
bool cmp(const int &a, const int &b) { return c[a] < c[b]; }
int pd[300050], pd2[300050];
map<int, int> mp[300050];
inline unsigned long long geths(int id, int l, int r) {
  --l;
  --r;
  if (!l) return hs[id][r];
  return hs[id][r] - hs[id][l - 1] * po[r - l + 1];
}
inline void del1(int);
inline void del2(int);
inline void del1(int id) {
  if (!pd[id]) return;
  pd[id] = 0;
  for (map<int, int>::iterator x = mp[id].begin(); x != mp[id].end(); ++x)
    del2((*x).first);
  mp[id].clear();
}
inline void del2(int id) {
  if (!pd2[id]) return;
  pd2[id] = 0;
  for (int i = 0; i < v[id].size(); ++i) del1(v[id][i]);
  v[id].clear();
  return;
}
inline void work(int a, int pos, int b) {
  int len = min(v[a].size() - pos + 1, v[b].size());
  if (geths(a, pos, pos + len - 1) != geths(b, 1, len)) {
    del2(a);
    del2(b);
  } else {
    pd2[b] = 0;
    int ok = 1;
    for (int j = len, x; j < v[b].size(); ++j) {
      x = v[b][j];
      v[a].push_back(x);
      hs[a].push_back(p * hs[a][hs[a].size() - 1] + x);
      if (pd[x]) {
        if (mp[x][a]) {
          ok = 0;
        } else
          mp[x][a] = v[a].size();
      } else
        ok = 0;
    }
    if (!ok) del2(a);
  }
}
int cnt[300050];
int main() {
  n = read();
  m = read();
  k = read();
  po[0] = 1;
  for (int i = 1; i <= 300000; ++i) po[i] = po[i - 1] * p;
  for (int i = 1; i <= n; ++i) pd2[i] = 1;
  for (int i = 1; i <= k; ++i) pd[i] = 1;
  for (int i = 1, ok; i <= n; ++i) {
    c[i] = read();
    ok = 1;
    for (int j = 1, x; j <= c[i]; ++j) {
      x = read();
      v[i].push_back(x);
      if (j == 1)
        hs[i].push_back(x);
      else
        hs[i].push_back(p * hs[i][hs[i].size() - 1] + x);
      if (pd[x]) {
        if (mp[x][i])
          ok = 0;
        else
          mp[x][i] = j;
      } else
        ok = 0;
    }
    if (!ok) del2(i);
  }
  for (int i = 1, t; i <= n; ++i) {
    if (!pd2[i]) continue;
    t = v[i][0];
    if (!pd[t] || mp[t].size() == 1) continue;
    for (map<int, int>::iterator x = mp[t].begin(); x != mp[t].end(); ++x) {
      if ((*x).first == i || !pd2[(*x).first]) continue;
      work((*x).first, (*x).second, i);
      break;
    }
    if (mp[t][i]) mp[t].erase(mp[t].find(i));
  }
  for (int i = 1, len; i <= k; ++i) {
    if (!pd[i]) continue;
    len = 0;
    for (map<int, int>::iterator x = mp[i].begin(); x != mp[i].end(); ++x) {
      if (!pd2[(*x).first]) continue;
      if (len) {
        del1(i);
        break;
      } else
        len = 1;
    }
  }
  for (int i = 1; i <= n; ++i)
    if (pd2[i]) ++cnt[v[i].size()];
  for (int i = 1; i <= k; ++i)
    if (pd[i] && !mp[i].size()) ++cnt[1];
  for (int i = 1; i <= k; ++i)
    if (cnt[i]) al[++al[0]] = i;
  dp[0] = 1;
  for (int j = 0; j <= m; ++j)
    for (int i = 1; i <= al[0]; ++i)
      if (j + al[i] <= m)
        dp[j + al[i]] = (1ll * cnt[al[i]] * dp[j] + dp[j + al[i]]) % mod;
  cout << dp[m] << endl;
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

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>
using namespace std;
const int mod = 998244353;
const unsigned long long p = 19260817;
inline int read(int x = 0, char c = getchar(), bool f = 0) {
  while (c < '0' || c > '9') f = c == '-', c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
  return f ? -x : x;
}
int n, m, k;
int c[300050], dp[300050], al[300050];
vector<int> v[300050];
vector<unsigned long long> hs[300050];
unsigned long long po[300050];
bool cmp(const int &a, const int &b) { return c[a] < c[b]; }
int pd[300050], pd2[300050];
map<int, int> mp[300050];
inline unsigned long long geths(int id, int l, int r) {
  --l;
  --r;
  if (!l) return hs[id][r];
  return hs[id][r] - hs[id][l - 1] * po[r - l + 1];
}
inline void del1(int);
inline void del2(int);
inline void del1(int id) {
  if (!pd[id]) return;
  pd[id] = 0;
  for (map<int, int>::iterator x = mp[id].begin(); x != mp[id].end(); ++x)
    del2((*x).first);
  mp[id].clear();
}
inline void del2(int id) {
  if (!pd2[id]) return;
  pd2[id] = 0;
  for (int i = 0; i < v[id].size(); ++i) del1(v[id][i]);
  v[id].clear();
  return;
}
inline void work(int a, int pos, int b) {
  int len = min(v[a].size() - pos + 1, v[b].size());
  if (geths(a, pos, pos + len - 1) != geths(b, 1, len)) {
    del2(a);
    del2(b);
  } else {
    pd2[b] = 0;
    int ok = 1;
    for (int j = len, x; j < v[b].size(); ++j) {
      x = v[b][j];
      v[a].push_back(x);
      hs[a].push_back(p * hs[a][hs[a].size() - 1] + x);
      if (pd[x]) {
        if (mp[x][a]) {
          ok = 0;
        } else
          mp[x][a] = v[a].size();
      } else
        ok = 0;
    }
    if (!ok) del2(a);
  }
}
int cnt[300050];
int main() {
  n = read();
  m = read();
  k = read();
  po[0] = 1;
  for (int i = 1; i <= 300000; ++i) po[i] = po[i - 1] * p;
  for (int i = 1; i <= n; ++i) pd2[i] = 1;
  for (int i = 1; i <= k; ++i) pd[i] = 1;
  for (int i = 1, ok; i <= n; ++i) {
    c[i] = read();
    ok = 1;
    for (int j = 1, x; j <= c[i]; ++j) {
      x = read();
      v[i].push_back(x);
      if (j == 1)
        hs[i].push_back(x);
      else
        hs[i].push_back(p * hs[i][hs[i].size() - 1] + x);
      if (pd[x]) {
        if (mp[x][i])
          ok = 0;
        else
          mp[x][i] = j;
      } else
        ok = 0;
    }
    if (!ok) del2(i);
  }
  for (int i = 1, t; i <= n; ++i) {
    if (!pd2[i]) continue;
    t = v[i][0];
    if (!pd[t] || mp[t].size() == 1) continue;
    for (map<int, int>::iterator x = mp[t].begin(); x != mp[t].end(); ++x) {
      if ((*x).first == i || !pd2[(*x).first]) continue;
      work((*x).first, (*x).second, i);
      break;
    }
    if (mp[t][i]) mp[t].erase(mp[t].find(i));
  }
  for (int i = 1, len; i <= k; ++i) {
    if (!pd[i]) continue;
    len = 0;
    for (map<int, int>::iterator x = mp[i].begin(); x != mp[i].end(); ++x) {
      if (!pd2[(*x).first]) continue;
      if (len) {
        del1(i);
        break;
      } else
        len = 1;
    }
  }
  for (int i = 1; i <= n; ++i)
    if (pd2[i]) ++cnt[v[i].size()];
  for (int i = 1; i <= k; ++i)
    if (pd[i] && !mp[i].size()) ++cnt[1];
  for (int i = 1; i <= k; ++i)
    if (cnt[i]) al[++al[0]] = i;
  dp[0] = 1;
  for (int j = 0; j <= m; ++j)
    for (int i = 1; i <= al[0]; ++i)
      if (j + al[i] <= m)
        dp[j + al[i]] = (1ll * cnt[al[i]] * dp[j] + dp[j + al[i]]) % mod;
  cout << dp[m] << endl;
  return 0;
}

```