#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const long long mod = 998244353;
inline long long gcd(long long a, long long b) {
  return !b ? a : gcd(b, a % b);
}
inline long long q_pow(long long a, long long x = mod - 2) {
  long long ans = 1, tmp = a;
  while (x) {
    if (x & 1) (ans *= tmp) %= mod;
    (tmp *= tmp) %= mod;
    x >>= 1;
  }
  return ans;
}
template <typename T>
inline void re(T &N) {
  int f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  N = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') N = N * 10 + c - '0';
  N *= f;
}
template <class T, class... T_>
inline void re(T &x, T_ &...y) {
  re(x), re(y...);
}
int m, n, k, t = 1, st, en;
int vis[N];
int cnt[N];
long long dp[N];
vector<int> in[N], out[N];
inline void add(int x, int y) {
  in[y].push_back(x);
  out[x].push_back(y);
}
int bad[N];
void expand(int x) {
  if (bad[x]) return;
  bad[x] = 1;
  for (int i : in[x]) expand(i);
  for (int i : out[x]) expand(i);
}
vector<int> v[N];
int main() {
  re(n, m, k);
  for (int i = 1; i <= n; i++) {
    int len;
    re(len);
    v[i] = vector<int>(len);
    for (int j = 0; j < len; j++) re(v[i][j]);
    for (int j = 0; j + 1 < len; j++) add(v[i][j], v[i][j + 1]);
  }
  for (int i = 1; i <= n; i++) {
    if (set<int>(v[i].begin(), v[i].end()).size() != v[i].size())
      for (int j : v[i]) expand(j);
  }
  for (int i = 1; i <= k; i++) {
    sort(in[i].begin(), in[i].end());
    in[i].erase(unique(in[i].begin(), in[i].end()), in[i].end());
    sort(out[i].begin(), out[i].end());
    out[i].erase(unique(out[i].begin(), out[i].end()), out[i].end());
  }
  for (int i = 1; i <= k; i++) {
    if (bad[i]) continue;
    if (in[i].size() > 1 || out[i].size() > 1) {
      expand(i);
      continue;
    }
    if (vis[i]) continue;
    queue<int> q;
    q.push(i);
    vis[i] = 1;
    int ok = 1;
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int j : out[x]) {
        if (vis[j]) {
          ok = 0;
          break;
        }
        vis[j] = 1;
        q.push(j);
      }
      if (!ok) {
        expand(x);
        break;
      }
    }
    if (ok) {
      q.push(i);
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int j : in[x]) {
          if (vis[j]) continue;
          vis[j] = 1;
          q.push(j);
        }
      }
    }
  }
  fill(vis + 1, vis + k + 1, 0);
  for (int i = 1; i <= k; i++)
    if (!bad[i] && !vis[i]) {
      int sum = 1;
      queue<int> q;
      q.push(i);
      vis[i] = 1;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int j : in[x]) {
          if (vis[j]) continue;
          sum++;
          vis[j] = 1;
          q.push(j);
        }
        for (int j : out[x]) {
          if (vis[j]) continue;
          sum++;
          vis[j] = 1;
          q.push(j);
        }
      }
      cnt[sum]++;
    }
  vector<int> key;
  for (int i = 1; i <= m; i++)
    if (cnt[i]) key.push_back(i);
  dp[0] = 1;
  for (int i = 1; i <= m; i++)
    for (int j : key)
      if (i >= j) (dp[i] += dp[i - j] * cnt[j] % mod) %= mod;
  printf("%lld\n", dp[m]);
}

### 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 N = 1e6 + 10;
const long long mod = 998244353;
inline long long gcd(long long a, long long b) {
  return !b ? a : gcd(b, a % b);
}
inline long long q_pow(long long a, long long x = mod - 2) {
  long long ans = 1, tmp = a;
  while (x) {
    if (x & 1) (ans *= tmp) %= mod;
    (tmp *= tmp) %= mod;
    x >>= 1;
  }
  return ans;
}
template <typename T>
inline void re(T &N) {
  int f = 1;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') f = -1;
  N = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') N = N * 10 + c - '0';
  N *= f;
}
template <class T, class... T_>
inline void re(T &x, T_ &...y) {
  re(x), re(y...);
}
int m, n, k, t = 1, st, en;
int vis[N];
int cnt[N];
long long dp[N];
vector<int> in[N], out[N];
inline void add(int x, int y) {
  in[y].push_back(x);
  out[x].push_back(y);
}
int bad[N];
void expand(int x) {
  if (bad[x]) return;
  bad[x] = 1;
  for (int i : in[x]) expand(i);
  for (int i : out[x]) expand(i);
}
vector<int> v[N];
int main() {
  re(n, m, k);
  for (int i = 1; i <= n; i++) {
    int len;
    re(len);
    v[i] = vector<int>(len);
    for (int j = 0; j < len; j++) re(v[i][j]);
    for (int j = 0; j + 1 < len; j++) add(v[i][j], v[i][j + 1]);
  }
  for (int i = 1; i <= n; i++) {
    if (set<int>(v[i].begin(), v[i].end()).size() != v[i].size())
      for (int j : v[i]) expand(j);
  }
  for (int i = 1; i <= k; i++) {
    sort(in[i].begin(), in[i].end());
    in[i].erase(unique(in[i].begin(), in[i].end()), in[i].end());
    sort(out[i].begin(), out[i].end());
    out[i].erase(unique(out[i].begin(), out[i].end()), out[i].end());
  }
  for (int i = 1; i <= k; i++) {
    if (bad[i]) continue;
    if (in[i].size() > 1 || out[i].size() > 1) {
      expand(i);
      continue;
    }
    if (vis[i]) continue;
    queue<int> q;
    q.push(i);
    vis[i] = 1;
    int ok = 1;
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      for (int j : out[x]) {
        if (vis[j]) {
          ok = 0;
          break;
        }
        vis[j] = 1;
        q.push(j);
      }
      if (!ok) {
        expand(x);
        break;
      }
    }
    if (ok) {
      q.push(i);
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int j : in[x]) {
          if (vis[j]) continue;
          vis[j] = 1;
          q.push(j);
        }
      }
    }
  }
  fill(vis + 1, vis + k + 1, 0);
  for (int i = 1; i <= k; i++)
    if (!bad[i] && !vis[i]) {
      int sum = 1;
      queue<int> q;
      q.push(i);
      vis[i] = 1;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int j : in[x]) {
          if (vis[j]) continue;
          sum++;
          vis[j] = 1;
          q.push(j);
        }
        for (int j : out[x]) {
          if (vis[j]) continue;
          sum++;
          vis[j] = 1;
          q.push(j);
        }
      }
      cnt[sum]++;
    }
  vector<int> key;
  for (int i = 1; i <= m; i++)
    if (cnt[i]) key.push_back(i);
  dp[0] = 1;
  for (int i = 1; i <= m; i++)
    for (int j : key)
      if (i >= j) (dp[i] += dp[i - j] * cnt[j] % mod) %= mod;
  printf("%lld\n", dp[m]);
}

```