#include <bits/stdc++.h>
using namespace std;
namespace mypoly {
const int MOD = 998244353;
const int g = 3;
int qmul(int x, int y) { return 1ll * x * y - 1ll * x * y / MOD * MOD; }
int qadd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
int G[21][(1 << 20) + 1], R[21][(1 << 20) + 1], inver[(1 << 20) + 1];
int quick(int A, int B) {
  int res = 1;
  while (B) {
    if (B & 1) res = qmul(res, A);
    A = qmul(A, A);
    B >>= 1;
  }
  return res;
}
int inv(int x) { return quick(x, MOD - 2); }
struct POLY {
  int len;
  int rev[1 << 20];
  POLY() {
    for (int i = 1; i <= (1 << 20); ++i) inver[i] = inv(i);
    for (int i = 1; i <= 20; ++i) {
      G[i][0] = 1;
      R[i][0] = 1;
      int tmp2 = inv(quick(g, (MOD - 1) >> i));
      int tmp = quick(g, (MOD - 1) >> i);
      for (int j = 1; j <= (1 << i); ++j) {
        G[i][j] = qmul(G[i][j - 1], tmp);
        R[i][j] = qmul(R[i][j - 1], tmp2);
      }
    }
  }
  void butterfly(vector<int>& v) {
    for (int i = 0; i < len; ++i) {
      rev[i] = rev[i >> 1] >> 1;
      if (i & 1) rev[i] |= len >> 1;
    }
    for (int i = 0; i < len; ++i)
      if (rev[i] > i) swap(v[i], v[rev[i]]);
  }
  vector<int> ntt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(B, G[lg][k]);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  vector<int> intt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(R[lg][k], B);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  void getlen(int x) {
    len = 1;
    while (len < x) {
      len <<= 1;
    }
  }
  vector<int> mul(vector<int> A, vector<int> B) {
    if (A.size() + B.size() <= 25) {
      vector<int> ret(A.size() + B.size() - 1);
      for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < B.size(); ++j)
          ret[i + j] = qadd(ret[i + j], qmul(A[i], B[j]));
      return ret;
    }
    getlen(A.size() + B.size());
    A.resize(len);
    B.resize(len);
    A = ntt(A);
    B = ntt(B);
    for (int i = 0; i < len; ++i) A[i] = qmul(A[i], B[i]);
    A = intt(A);
    int iv = inver[len];
    for (int i = 0; i < len; ++i) {
      A[i] = qmul(A[i], iv);
    }
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
  }
  vector<int> inverse(vector<int> A, int n) {
    vector<int> ret(n);
    if (n == 1) {
      ret[0] = quick(A[0], MOD - 2);
    } else {
      vector<int> oth = inverse(A, (n + 1) >> 1);
      ret = oth;
      ret.resize(n);
      for (int i = 0; i < n; ++i) ret[i] = (ret[i] + ret[i]) % MOD;
      getlen((oth.size() << 1) + A.size());
      oth.resize(len);
      A.resize(len);
      oth = ntt(oth);
      A = ntt(A);
      for (int i = 0; i < len; ++i) oth[i] = qmul(qmul(oth[i], oth[i]), A[i]);
      oth = intt(oth);
      oth.resize(n);
      int iv = inver[len];
      for (int i = 0; i < n; ++i) {
        oth[i] = qmul(oth[i], iv);
      }
      for (int i = 0; i < n; ++i) ret[i] = qadd(ret[i], MOD - oth[i]);
    }
    return ret;
  }
} poly;
vector<int> operator*(vector<int> A, vector<int> B) { return poly.mul(A, B); }
vector<int> operator+(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], B[i]);
  return A;
}
vector<int> operator-(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], MOD - B[i]);
  return A;
}
vector<int> operator/(vector<int> A, vector<int> B) {
  return A * poly.inverse(B, A.size() - B.size() + 1);
}
vector<int> operator%(vector<int> A, vector<int> B) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  while (B.size() != 1 && B.back() == 0) B.pop_back();
  if (B.size() > A.size()) return A;
  vector<int> rem, mod;
  int n, m;
  n = A.size() - 1;
  m = B.size() - 1;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem = A / B;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem.resize(n - m + 1);
  reverse(rem.begin(), rem.end());
  mod = A - rem * B;
  mod.resize(m);
  return mod;
}
vector<int> der(vector<int> A) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  vector<int> ret(A.size() - 1);
  for (int i = 0; i < ret.size(); ++i) ret[i] = 1ll * (i + 1) * A[i + 1] % MOD;
  if (ret.empty()) return vector<int>(1, 0);
  return ret;
}
}  // namespace mypoly
using namespace mypoly;
const int INF = 0x3f3f3f3f;
const int MAXN = 6e5 + 1;
int n, m, k;
vector<int> A[MAXN];
vector<int> Z[MAXN];
int fa[MAXN];
bool ba[MAXN];
vector<int> belong[MAXN];
int root(int x) { return fa[x] = (fa[x] == x ? x : root(fa[x])); }
void merge(int u, int v) { fa[root(u)] = root(v); }
void add(int& A, int B) {
  A += B;
  if (A >= MOD) A -= MOD;
}
int nex[MAXN];
int main() {
  for (int i = 0; i < MAXN; ++i) fa[i] = i, nex[i] = -1;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) {
    int ci;
    scanf("%d", &ci);
    A[i].resize(ci);
    for (int j = 0; j < ci; ++j) scanf("%d", &A[i][j]);
    map<int, int> app;
    bool bad = 0;
    for (auto it : A[i]) {
      if (app.find(it) != app.end()) {
        bad = 1;
        break;
      }
      app[it] = 1;
    }
    if (bad) {
      ba[i] = 1;
    }
    for (auto it : A[i]) Z[it].push_back(i);
  }
  for (int i = 1; i <= k; ++i) {
    A[++n] = {i};
    Z[i].push_back(n);
  }
  for (int i = 1; i <= k; ++i) {
    if (Z[i].size() > 1) {
      for (int j = 0; j < Z[i].size() - 1; ++j) {
        merge(Z[i][j], Z[i][j + 1]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) ba[root(i)] |= ba[i];
  for (int i = 1; i <= n; ++i) ba[i] |= ba[root(i)];
  for (int i = 1; i <= n; ++i) belong[root(i)].push_back(i);
  vector<int> Tmp(m + 1, 0);
  vector<int> orz;
  for (int i = 1; i <= n; ++i)
    if (root(i) == i && !ba[i]) {
      vector<int>& now = belong[i];
      map<int, int> app;
      bool bad = 0;
      for (auto it : now) {
        for (auto itt : A[it]) {
          app[itt] = 1;
        }
        if (A[it].size() > 1) {
          for (int j = 0; j < A[it].size() - 1; ++j) {
            if (nex[A[it][j]] != A[it][j + 1] && nex[A[it][j]] != -1) {
              bad = 1;
            }
            nex[A[it][j]] = A[it][j + 1];
          }
        }
      }
      if (bad) continue;
      map<int, int> app2 = app;
      int sz = app2.size();
      for (auto ite = app2.begin(); ite != app2.end(); ite++)
        if (app.find(nex[ite->first]) != app.end()) app.erase(nex[ite->first]);
      if (app.size() != 1) {
        continue;
      }
      int fi = app.begin()->first;
      app2.clear();
      while (true) {
        if (fi == -1) break;
        if (app2.find(fi) != app2.end()) {
          bad = 1;
          break;
        }
        app2[fi] = 1;
        fi = nex[fi];
      }
      if (!bad && sz <= m && app2.size() == sz) {
        Tmp[sz]++;
        orz.push_back(sz);
      }
    }
  for (auto& it : Tmp) it = (MOD - it) % MOD;
  Tmp[0] = 1;
  Tmp = poly.inverse(Tmp, m + 1);
  cout << Tmp[m] << endl;
  return 0;
}

### Prompt

Your challenge is to write 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;
namespace mypoly {
const int MOD = 998244353;
const int g = 3;
int qmul(int x, int y) { return 1ll * x * y - 1ll * x * y / MOD * MOD; }
int qadd(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
int G[21][(1 << 20) + 1], R[21][(1 << 20) + 1], inver[(1 << 20) + 1];
int quick(int A, int B) {
  int res = 1;
  while (B) {
    if (B & 1) res = qmul(res, A);
    A = qmul(A, A);
    B >>= 1;
  }
  return res;
}
int inv(int x) { return quick(x, MOD - 2); }
struct POLY {
  int len;
  int rev[1 << 20];
  POLY() {
    for (int i = 1; i <= (1 << 20); ++i) inver[i] = inv(i);
    for (int i = 1; i <= 20; ++i) {
      G[i][0] = 1;
      R[i][0] = 1;
      int tmp2 = inv(quick(g, (MOD - 1) >> i));
      int tmp = quick(g, (MOD - 1) >> i);
      for (int j = 1; j <= (1 << i); ++j) {
        G[i][j] = qmul(G[i][j - 1], tmp);
        R[i][j] = qmul(R[i][j - 1], tmp2);
      }
    }
  }
  void butterfly(vector<int>& v) {
    for (int i = 0; i < len; ++i) {
      rev[i] = rev[i >> 1] >> 1;
      if (i & 1) rev[i] |= len >> 1;
    }
    for (int i = 0; i < len; ++i)
      if (rev[i] > i) swap(v[i], v[rev[i]]);
  }
  vector<int> ntt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(B, G[lg][k]);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  vector<int> intt(vector<int> v) {
    butterfly(v);
    vector<int> nex;
    int lg = 1;
    for (int l = 2; l <= len; l <<= 1, ++lg) {
      nex.clear();
      nex.resize(len);
      for (int j = 0; j < len; j += l) {
        for (int k = 0; k < l / 2; ++k) {
          int A, B;
          A = v[j + k];
          B = v[j + l / 2 + k];
          B = qmul(R[lg][k], B);
          nex[j + k] = qadd(A, B);
          nex[j + k + l / 2] = qadd(A, MOD - B);
        }
      }
      v = nex;
    }
    return v;
  }
  void getlen(int x) {
    len = 1;
    while (len < x) {
      len <<= 1;
    }
  }
  vector<int> mul(vector<int> A, vector<int> B) {
    if (A.size() + B.size() <= 25) {
      vector<int> ret(A.size() + B.size() - 1);
      for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < B.size(); ++j)
          ret[i + j] = qadd(ret[i + j], qmul(A[i], B[j]));
      return ret;
    }
    getlen(A.size() + B.size());
    A.resize(len);
    B.resize(len);
    A = ntt(A);
    B = ntt(B);
    for (int i = 0; i < len; ++i) A[i] = qmul(A[i], B[i]);
    A = intt(A);
    int iv = inver[len];
    for (int i = 0; i < len; ++i) {
      A[i] = qmul(A[i], iv);
    }
    while (!A.empty() && A.back() == 0) A.pop_back();
    return A;
  }
  vector<int> inverse(vector<int> A, int n) {
    vector<int> ret(n);
    if (n == 1) {
      ret[0] = quick(A[0], MOD - 2);
    } else {
      vector<int> oth = inverse(A, (n + 1) >> 1);
      ret = oth;
      ret.resize(n);
      for (int i = 0; i < n; ++i) ret[i] = (ret[i] + ret[i]) % MOD;
      getlen((oth.size() << 1) + A.size());
      oth.resize(len);
      A.resize(len);
      oth = ntt(oth);
      A = ntt(A);
      for (int i = 0; i < len; ++i) oth[i] = qmul(qmul(oth[i], oth[i]), A[i]);
      oth = intt(oth);
      oth.resize(n);
      int iv = inver[len];
      for (int i = 0; i < n; ++i) {
        oth[i] = qmul(oth[i], iv);
      }
      for (int i = 0; i < n; ++i) ret[i] = qadd(ret[i], MOD - oth[i]);
    }
    return ret;
  }
} poly;
vector<int> operator*(vector<int> A, vector<int> B) { return poly.mul(A, B); }
vector<int> operator+(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], B[i]);
  return A;
}
vector<int> operator-(vector<int> A, vector<int> B) {
  int Sz = max(A.size(), B.size());
  A.resize(Sz);
  for (int i = 0; i < B.size(); ++i) A[i] = qadd(A[i], MOD - B[i]);
  return A;
}
vector<int> operator/(vector<int> A, vector<int> B) {
  return A * poly.inverse(B, A.size() - B.size() + 1);
}
vector<int> operator%(vector<int> A, vector<int> B) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  while (B.size() != 1 && B.back() == 0) B.pop_back();
  if (B.size() > A.size()) return A;
  vector<int> rem, mod;
  int n, m;
  n = A.size() - 1;
  m = B.size() - 1;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem = A / B;
  reverse(A.begin(), A.end());
  reverse(B.begin(), B.end());
  rem.resize(n - m + 1);
  reverse(rem.begin(), rem.end());
  mod = A - rem * B;
  mod.resize(m);
  return mod;
}
vector<int> der(vector<int> A) {
  while (A.size() != 1 && A.back() == 0) A.pop_back();
  vector<int> ret(A.size() - 1);
  for (int i = 0; i < ret.size(); ++i) ret[i] = 1ll * (i + 1) * A[i + 1] % MOD;
  if (ret.empty()) return vector<int>(1, 0);
  return ret;
}
}  // namespace mypoly
using namespace mypoly;
const int INF = 0x3f3f3f3f;
const int MAXN = 6e5 + 1;
int n, m, k;
vector<int> A[MAXN];
vector<int> Z[MAXN];
int fa[MAXN];
bool ba[MAXN];
vector<int> belong[MAXN];
int root(int x) { return fa[x] = (fa[x] == x ? x : root(fa[x])); }
void merge(int u, int v) { fa[root(u)] = root(v); }
void add(int& A, int B) {
  A += B;
  if (A >= MOD) A -= MOD;
}
int nex[MAXN];
int main() {
  for (int i = 0; i < MAXN; ++i) fa[i] = i, nex[i] = -1;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) {
    int ci;
    scanf("%d", &ci);
    A[i].resize(ci);
    for (int j = 0; j < ci; ++j) scanf("%d", &A[i][j]);
    map<int, int> app;
    bool bad = 0;
    for (auto it : A[i]) {
      if (app.find(it) != app.end()) {
        bad = 1;
        break;
      }
      app[it] = 1;
    }
    if (bad) {
      ba[i] = 1;
    }
    for (auto it : A[i]) Z[it].push_back(i);
  }
  for (int i = 1; i <= k; ++i) {
    A[++n] = {i};
    Z[i].push_back(n);
  }
  for (int i = 1; i <= k; ++i) {
    if (Z[i].size() > 1) {
      for (int j = 0; j < Z[i].size() - 1; ++j) {
        merge(Z[i][j], Z[i][j + 1]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) ba[root(i)] |= ba[i];
  for (int i = 1; i <= n; ++i) ba[i] |= ba[root(i)];
  for (int i = 1; i <= n; ++i) belong[root(i)].push_back(i);
  vector<int> Tmp(m + 1, 0);
  vector<int> orz;
  for (int i = 1; i <= n; ++i)
    if (root(i) == i && !ba[i]) {
      vector<int>& now = belong[i];
      map<int, int> app;
      bool bad = 0;
      for (auto it : now) {
        for (auto itt : A[it]) {
          app[itt] = 1;
        }
        if (A[it].size() > 1) {
          for (int j = 0; j < A[it].size() - 1; ++j) {
            if (nex[A[it][j]] != A[it][j + 1] && nex[A[it][j]] != -1) {
              bad = 1;
            }
            nex[A[it][j]] = A[it][j + 1];
          }
        }
      }
      if (bad) continue;
      map<int, int> app2 = app;
      int sz = app2.size();
      for (auto ite = app2.begin(); ite != app2.end(); ite++)
        if (app.find(nex[ite->first]) != app.end()) app.erase(nex[ite->first]);
      if (app.size() != 1) {
        continue;
      }
      int fi = app.begin()->first;
      app2.clear();
      while (true) {
        if (fi == -1) break;
        if (app2.find(fi) != app2.end()) {
          bad = 1;
          break;
        }
        app2[fi] = 1;
        fi = nex[fi];
      }
      if (!bad && sz <= m && app2.size() == sz) {
        Tmp[sz]++;
        orz.push_back(sz);
      }
    }
  for (auto& it : Tmp) it = (MOD - it) % MOD;
  Tmp[0] = 1;
  Tmp = poly.inverse(Tmp, m + 1);
  cout << Tmp[m] << endl;
  return 0;
}

```