#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T1, typename T2>
inline void remin(T1& a, T2 b) {
  a = min(a, (T1)b);
}
template <typename T1, typename T2>
inline void remax(T1& a, T2 b) {
  a = max(a, (T1)b);
}
const int LOG = 19, maxN = 1 << LOG, mod = 998244353;
template <typename T1, typename T2>
inline void addMod(T1& a, T2 b) {
  a = (a + b) % mod;
}
template <typename T1, typename T2>
inline void multMod(T1& a, T2 b) {
  a = a * b % mod;
}
int vis[maxN], nxt[maxN], prv[maxN], T[maxN];
long long dp[maxN];
bool ban[maxN];
void fail() {
  printf("0\n");
  exit(0);
}
map<int, int> M;
vector<pair<int, int> > kys;
void solve() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int v = (1); v < (n + 1); v++) {
    int c;
    scanf("%d", &c);
    bool dupl = false;
    for (int i = (0); i < (c); i++) {
      scanf("%d", T + i);
      if (vis[T[i]] == v) dupl = true;
      vis[T[i]] = v;
    }
    if (dupl) {
      for (int i = (0); i < (c); i++) ban[T[i]] = true;
      continue;
    }
    for (int i = (0); i < (c - 1); i++) {
      int x = T[i];
      if (nxt[x] != 0 and nxt[x] != T[i + 1])
        ban[x] = ban[nxt[x]] = true;
      else
        nxt[x] = T[i + 1];
    }
    for (int i = (1); i < (c); i++) {
      int x = T[i];
      if (prv[x] != 0 and prv[x] != T[i - 1])
        ban[x] = ban[prv[x]] = true;
      else
        prv[x] = T[i - 1];
    }
  }
  for (int v = (1); v < (k + 1); v++)
    if (prv[v] == 0) {
      int d = 0;
      bool ok = true;
      for (int x = v; x != 0; x = nxt[x]) {
        d++;
        if (ban[x] or (x == v and d != 1)) {
          ok = false;
          break;
        }
      }
      if (ok) M[d]++;
    }
  for (auto it : M) kys.push_back(it);
  dp[0] = 1;
  for (int i = (1); i < (m + 1); i++) {
    for (int j = (0); j < (((int)(kys).size())); j++) {
      int ki, vl;
      tie(ki, vl) = kys[j];
      if (ki <= i) dp[i] += dp[i - ki] * vl;
    }
    dp[i] %= mod;
  }
  printf("%lld\n", dp[m]);
}
int main() {
  int t = 1;
  for (int tid = (1); tid < (t + 1); tid++) {
    solve();
  }
  return 0;
}

### Prompt

Generate 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>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T1, typename T2>
inline void remin(T1& a, T2 b) {
  a = min(a, (T1)b);
}
template <typename T1, typename T2>
inline void remax(T1& a, T2 b) {
  a = max(a, (T1)b);
}
const int LOG = 19, maxN = 1 << LOG, mod = 998244353;
template <typename T1, typename T2>
inline void addMod(T1& a, T2 b) {
  a = (a + b) % mod;
}
template <typename T1, typename T2>
inline void multMod(T1& a, T2 b) {
  a = a * b % mod;
}
int vis[maxN], nxt[maxN], prv[maxN], T[maxN];
long long dp[maxN];
bool ban[maxN];
void fail() {
  printf("0\n");
  exit(0);
}
map<int, int> M;
vector<pair<int, int> > kys;
void solve() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int v = (1); v < (n + 1); v++) {
    int c;
    scanf("%d", &c);
    bool dupl = false;
    for (int i = (0); i < (c); i++) {
      scanf("%d", T + i);
      if (vis[T[i]] == v) dupl = true;
      vis[T[i]] = v;
    }
    if (dupl) {
      for (int i = (0); i < (c); i++) ban[T[i]] = true;
      continue;
    }
    for (int i = (0); i < (c - 1); i++) {
      int x = T[i];
      if (nxt[x] != 0 and nxt[x] != T[i + 1])
        ban[x] = ban[nxt[x]] = true;
      else
        nxt[x] = T[i + 1];
    }
    for (int i = (1); i < (c); i++) {
      int x = T[i];
      if (prv[x] != 0 and prv[x] != T[i - 1])
        ban[x] = ban[prv[x]] = true;
      else
        prv[x] = T[i - 1];
    }
  }
  for (int v = (1); v < (k + 1); v++)
    if (prv[v] == 0) {
      int d = 0;
      bool ok = true;
      for (int x = v; x != 0; x = nxt[x]) {
        d++;
        if (ban[x] or (x == v and d != 1)) {
          ok = false;
          break;
        }
      }
      if (ok) M[d]++;
    }
  for (auto it : M) kys.push_back(it);
  dp[0] = 1;
  for (int i = (1); i < (m + 1); i++) {
    for (int j = (0); j < (((int)(kys).size())); j++) {
      int ki, vl;
      tie(ki, vl) = kys[j];
      if (ki <= i) dp[i] += dp[i - ki] * vl;
    }
    dp[i] %= mod;
  }
  printf("%lld\n", dp[m]);
}
int main() {
  int t = 1;
  for (int tid = (1); tid < (t + 1); tid++) {
    solve();
  }
  return 0;
}

```