#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
long long GcdExt(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = GcdExt(b, a % b, x, y);
  long long tmp = y;
  y = x - y * (a / b);
  x = tmp;
  return d;
}
struct ModInt {
  static constexpr int MOD = 998244353;
  int v = 0;
  ModInt() {}
  ModInt(long long x) {
    v = x % MOD;
    if (v < 0) v += MOD;
  }
  friend inline bool operator==(const ModInt& l, const ModInt& r) {
    return l.v == r.v;
  }
  friend inline bool operator!=(const ModInt& l, const ModInt& r) {
    return !(l == r);
  }
  ModInt& operator+=(const ModInt& r) {
    v += r.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt& r) {
    v -= r.v;
    if (v < 0) v += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    v = ((long long)v * r.v) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.Inv();
    return *this;
  }
  friend ModInt operator+(ModInt l, const ModInt& r) {
    l += r;
    return l;
  }
  friend ModInt operator-(ModInt l, const ModInt& r) {
    l -= r;
    return l;
  }
  friend ModInt operator*(ModInt l, const ModInt& r) {
    l *= r;
    return l;
  }
  friend ModInt operator/(ModInt l, const ModInt& r) {
    l /= r;
    return l;
  }
  ModInt Inv() const {
    long long x, y;
    assert(GcdExt(v, MOD, x, y) == 1);
    return x;
  }
  ModInt Pow(long long n) {
    if (!n) return 1;
    ModInt r = Pow(n >> 1);
    r *= r;
    if (n & 1) r *= v;
    return r;
  }
};
struct DisjointSet {
  vector<int> f;
  DisjointSet(int n = 0) { Reset(n); }
  void Reset(int n) {
    f.resize(n);
    iota(f.begin(), f.end(), 0);
  }
  int Find(int u) {
    if (f[u] == u) return u;
    return f[u] = Find(f[u]);
  }
  bool Merge(int s, int t) {
    s = Find(s);
    t = Find(t);
    if (s != t) {
      f[s] = t;
      return 1;
    }
    return 0;
  }
  void Add(int u) {
    int nf = int((f).size());
    if (u < nf) return;
    f.resize(u + 1);
    iota(f.begin() + nf, f.end(), nf);
  }
};
struct DirectedGraph {
  int n;
  vector<unordered_set<int>> adj;
  DirectedGraph(int n = 0) { Reset(n); }
  void Reset(int n) {
    this->n = n;
    adj.assign(n, {});
  }
  void AddEdge(int u, int v) { adj[u].insert(v); }
  vector<int> TarjanScc(vector<int>& comp_id) {
    comp_id.assign(n, -1);
    vector<int> comp_size;
    int dfsv = 0;
    vector<int> dfs(n, -1);
    vector<int> low(n);
    vector<int> st;
    vector<bool> in_st(n, 0);
    const std::function<void(int)> Dfs = [&](int u) {
      dfs[u] = dfsv++;
      low[u] = dfs[u];
      st.push_back(u);
      in_st[u] = 1;
      for (auto& v : (adj[u])) {
        if (dfs[v] < 0) {
          Dfs(v);
          low[u] = min(low[u], low[v]);
        } else if (in_st[v]) {
          low[u] = min(low[u], dfs[v]);
        }
      }
      if (low[u] == dfs[u]) {
        int c = 0;
        while (1) {
          int v = st.back();
          st.pop_back();
          in_st[v] = 0;
          comp_id[v] = int((comp_size).size());
          ++c;
          if (v == u) break;
        }
        comp_size.push_back(c);
      }
    };
    for (int i = 0; i < n; i++)
      if (dfs[i] < 0) {
        Dfs(i);
        assert(st.empty());
      }
    return comp_size;
  }
  vector<int> TopologicalSort() {
    vector<char> vis(n, 0);
    vector<int> ans;
    ans.reserve(n);
    const std::function<void(int)> Dfs = [&](int u) {
      vis[u] = 1;
      for (auto& v : (adj[u])) {
        if (!vis[v]) Dfs(v);
      }
      ans.push_back(u);
    };
    for (int i = 0; i < n; ++i)
      if (!vis[i]) Dfs(i);
    reverse((ans).begin(), (ans).end());
    return ans;
  }
};
int n, m, k;
vector<vector<int>> a;
vector<int> all;
vector<int> apos;
void Solve() {
  scanf("%d%d%d", &n, &m, &k);
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    int c;
    scanf("%d", &c);
    a[i].resize(c);
    for (auto& x : (a[i])) scanf("%d", &x);
  }
  DisjointSet ds(k + 1);
  vector<char> good_ch(k + 1, 1);
  {
    for (int i = 0; i < n; ++i) {
      for (auto& x : (a[i])) ds.Merge(a[i][0], x);
    }
    vector<int> cnt_ch(k + 1, 0);
    for (int i = 0; i < n; ++i) {
      for (auto& x : (a[i])) {
        cnt_ch[x]++;
      }
      bool good = 1;
      for (auto& x : (a[i])) {
        if (cnt_ch[x] > 1) good = 0;
        cnt_ch[x] = 0;
      }
      if (!good) good_ch[ds.Find(a[i][0])] = 0;
    }
  }
  DirectedGraph g(k + 1), g_rev(k + 1);
  for (int i = 0; i < n; ++i) {
    if (!good_ch[ds.Find(a[i][0])]) continue;
    for (int j = 1; j < int((a[i]).size()); ++j) {
      ds.Merge(a[i][j - 1], a[i][j]);
      g.AddEdge(a[i][j - 1], a[i][j]);
      g_rev.AddEdge(a[i][j], a[i][j - 1]);
    }
  }
  {
    for (int i = 1; i <= k; ++i) {
      if (int((g.adj[i]).size()) > 1 || int((g_rev.adj[i]).size()) > 1)
        good_ch[ds.Find(i)] = 0;
    }
    vector<int> comp_id;
    vector<int> comp_sizes = g.TarjanScc(comp_id);
    for (int i = 1; i <= k; ++i)
      if (comp_sizes[comp_id[i]] > 1) {
        good_ch[ds.Find(i)] = 0;
      }
  }
  vector<int> cnt_len(max(k, m) + 1, 0);
  {
    vector<int> top_order = g.TopologicalSort();
    vector<char> vis(k + 1, 0);
    vis[0] = 1;
    for (auto& x : (top_order)) {
      if (vis[x] || !good_ch[ds.Find(x)]) continue;
      int u = x;
      int len = 1;
      vis[u] = 1;
      while (!g.adj[u].empty()) {
        int v = *g.adj[u].begin();
        vis[v] = 1;
        len++;
        u = v;
      }
      42;
      cnt_len[len]++;
    }
  }
  vector<pair<int, int>> trans;
  for (int i = 1; i <= m; ++i)
    if (cnt_len[i] > 0) trans.emplace_back(i, cnt_len[i]);
  vector<ModInt> f(m + 1);
  f[0] = 1;
  for (int i = 1; i <= m; ++i) {
    f[i] = 0;
    for (auto& p : (trans)) {
      if (p.first > i) break;
      f[i] += f[i - p.first] * p.second;
    }
  }
  printf("%d\n", f[m].v);
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    Solve();
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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 double EPS = 1e-12;
const int INF = 1e9 + 10;
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
long long GcdExt(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = GcdExt(b, a % b, x, y);
  long long tmp = y;
  y = x - y * (a / b);
  x = tmp;
  return d;
}
struct ModInt {
  static constexpr int MOD = 998244353;
  int v = 0;
  ModInt() {}
  ModInt(long long x) {
    v = x % MOD;
    if (v < 0) v += MOD;
  }
  friend inline bool operator==(const ModInt& l, const ModInt& r) {
    return l.v == r.v;
  }
  friend inline bool operator!=(const ModInt& l, const ModInt& r) {
    return !(l == r);
  }
  ModInt& operator+=(const ModInt& r) {
    v += r.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  ModInt& operator-=(const ModInt& r) {
    v -= r.v;
    if (v < 0) v += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    v = ((long long)v * r.v) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.Inv();
    return *this;
  }
  friend ModInt operator+(ModInt l, const ModInt& r) {
    l += r;
    return l;
  }
  friend ModInt operator-(ModInt l, const ModInt& r) {
    l -= r;
    return l;
  }
  friend ModInt operator*(ModInt l, const ModInt& r) {
    l *= r;
    return l;
  }
  friend ModInt operator/(ModInt l, const ModInt& r) {
    l /= r;
    return l;
  }
  ModInt Inv() const {
    long long x, y;
    assert(GcdExt(v, MOD, x, y) == 1);
    return x;
  }
  ModInt Pow(long long n) {
    if (!n) return 1;
    ModInt r = Pow(n >> 1);
    r *= r;
    if (n & 1) r *= v;
    return r;
  }
};
struct DisjointSet {
  vector<int> f;
  DisjointSet(int n = 0) { Reset(n); }
  void Reset(int n) {
    f.resize(n);
    iota(f.begin(), f.end(), 0);
  }
  int Find(int u) {
    if (f[u] == u) return u;
    return f[u] = Find(f[u]);
  }
  bool Merge(int s, int t) {
    s = Find(s);
    t = Find(t);
    if (s != t) {
      f[s] = t;
      return 1;
    }
    return 0;
  }
  void Add(int u) {
    int nf = int((f).size());
    if (u < nf) return;
    f.resize(u + 1);
    iota(f.begin() + nf, f.end(), nf);
  }
};
struct DirectedGraph {
  int n;
  vector<unordered_set<int>> adj;
  DirectedGraph(int n = 0) { Reset(n); }
  void Reset(int n) {
    this->n = n;
    adj.assign(n, {});
  }
  void AddEdge(int u, int v) { adj[u].insert(v); }
  vector<int> TarjanScc(vector<int>& comp_id) {
    comp_id.assign(n, -1);
    vector<int> comp_size;
    int dfsv = 0;
    vector<int> dfs(n, -1);
    vector<int> low(n);
    vector<int> st;
    vector<bool> in_st(n, 0);
    const std::function<void(int)> Dfs = [&](int u) {
      dfs[u] = dfsv++;
      low[u] = dfs[u];
      st.push_back(u);
      in_st[u] = 1;
      for (auto& v : (adj[u])) {
        if (dfs[v] < 0) {
          Dfs(v);
          low[u] = min(low[u], low[v]);
        } else if (in_st[v]) {
          low[u] = min(low[u], dfs[v]);
        }
      }
      if (low[u] == dfs[u]) {
        int c = 0;
        while (1) {
          int v = st.back();
          st.pop_back();
          in_st[v] = 0;
          comp_id[v] = int((comp_size).size());
          ++c;
          if (v == u) break;
        }
        comp_size.push_back(c);
      }
    };
    for (int i = 0; i < n; i++)
      if (dfs[i] < 0) {
        Dfs(i);
        assert(st.empty());
      }
    return comp_size;
  }
  vector<int> TopologicalSort() {
    vector<char> vis(n, 0);
    vector<int> ans;
    ans.reserve(n);
    const std::function<void(int)> Dfs = [&](int u) {
      vis[u] = 1;
      for (auto& v : (adj[u])) {
        if (!vis[v]) Dfs(v);
      }
      ans.push_back(u);
    };
    for (int i = 0; i < n; ++i)
      if (!vis[i]) Dfs(i);
    reverse((ans).begin(), (ans).end());
    return ans;
  }
};
int n, m, k;
vector<vector<int>> a;
vector<int> all;
vector<int> apos;
void Solve() {
  scanf("%d%d%d", &n, &m, &k);
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    int c;
    scanf("%d", &c);
    a[i].resize(c);
    for (auto& x : (a[i])) scanf("%d", &x);
  }
  DisjointSet ds(k + 1);
  vector<char> good_ch(k + 1, 1);
  {
    for (int i = 0; i < n; ++i) {
      for (auto& x : (a[i])) ds.Merge(a[i][0], x);
    }
    vector<int> cnt_ch(k + 1, 0);
    for (int i = 0; i < n; ++i) {
      for (auto& x : (a[i])) {
        cnt_ch[x]++;
      }
      bool good = 1;
      for (auto& x : (a[i])) {
        if (cnt_ch[x] > 1) good = 0;
        cnt_ch[x] = 0;
      }
      if (!good) good_ch[ds.Find(a[i][0])] = 0;
    }
  }
  DirectedGraph g(k + 1), g_rev(k + 1);
  for (int i = 0; i < n; ++i) {
    if (!good_ch[ds.Find(a[i][0])]) continue;
    for (int j = 1; j < int((a[i]).size()); ++j) {
      ds.Merge(a[i][j - 1], a[i][j]);
      g.AddEdge(a[i][j - 1], a[i][j]);
      g_rev.AddEdge(a[i][j], a[i][j - 1]);
    }
  }
  {
    for (int i = 1; i <= k; ++i) {
      if (int((g.adj[i]).size()) > 1 || int((g_rev.adj[i]).size()) > 1)
        good_ch[ds.Find(i)] = 0;
    }
    vector<int> comp_id;
    vector<int> comp_sizes = g.TarjanScc(comp_id);
    for (int i = 1; i <= k; ++i)
      if (comp_sizes[comp_id[i]] > 1) {
        good_ch[ds.Find(i)] = 0;
      }
  }
  vector<int> cnt_len(max(k, m) + 1, 0);
  {
    vector<int> top_order = g.TopologicalSort();
    vector<char> vis(k + 1, 0);
    vis[0] = 1;
    for (auto& x : (top_order)) {
      if (vis[x] || !good_ch[ds.Find(x)]) continue;
      int u = x;
      int len = 1;
      vis[u] = 1;
      while (!g.adj[u].empty()) {
        int v = *g.adj[u].begin();
        vis[v] = 1;
        len++;
        u = v;
      }
      42;
      cnt_len[len]++;
    }
  }
  vector<pair<int, int>> trans;
  for (int i = 1; i <= m; ++i)
    if (cnt_len[i] > 0) trans.emplace_back(i, cnt_len[i]);
  vector<ModInt> f(m + 1);
  f[0] = 1;
  for (int i = 1; i <= m; ++i) {
    f[i] = 0;
    for (auto& p : (trans)) {
      if (p.first > i) break;
      f[i] += f[i - p.first] * p.second;
    }
  }
  printf("%d\n", f[m].v);
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; ++i) {
    Solve();
  }
  return 0;
}

```