You are the organizer of the famous "Zurich Music Festival". There will be n singers who will perform at the festival, identified by the integers 1, 2, ..., n. You must choose in which order they are going to perform on stage. 

You have m friends and each of them has a set of favourite singers. More precisely, for each 1≤ i≤ m, the i-th friend likes singers s_{i,1},   s_{i, 2},   ..., \,s_{i, q_i}.

A friend of yours is happy if the singers he likes perform consecutively (in an arbitrary order). An ordering of the singers is valid if it makes all your friends happy.

Compute the number of valid orderings modulo 998 244 353.

Input

The first line contains two integers n and m (1≤ n,\,m≤ 100) — the number of singers and the number of friends correspondingly.

The i-th of the next m lines contains the integer q_i (1≤ q_i≤ n) — the number of favorite singers of the i-th friend – followed by the q_i integers s_{i,1},   s_{i, 2},   ..., \,s_{i, q_i} (1≤ s_{i,1}<s_{i,2}<⋅⋅⋅<s_{i,q_i}≤ n) — the indexes of his favorite singers.

Output

Print the number of valid orderings of the singers modulo 998 244 353.

Examples

Input


3 1
2 1 3


Output


4


Input


5 5
2 1 2
2 2 3
2 3 4
2 4 5
2 1 5


Output


0


Input


100 1
1 50


Output


35305197


Input


5 1
5 1 2 3 4 5


Output


120


Input


2 5
1 2
1 2
1 2
1 1
1 1


Output


2


Input


11 4
5 4 5 7 9 11
2 2 10
2 9 11
7 1 2 3 5 8 10 11


Output


384

Note

Explanation of the first sample: There are 3 singers and only 1 friend. The friend likes the two singers 1 and 3. Thus, the 4 valid orderings are: 

  * 1 3 2
  * 2 1 3
  * 2 3 1
  * 3 1 2



Explanation of the second sample: There are 5 singers and 5 friends. One can show that no ordering is valid.

Explanation of the third sample: There are 100 singers and only 1 friend. The friend likes only singer 50, hence all the 100! possible orderings are valid.

Explanation of the fourth sample: There are 5 singers and only 1 friend. The friend likes all the singers, hence all the 5!=120 possible orderings are valid.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  static char _c;
  static bool _f;
  x = 0;
  _f = 0;
  _c = getchar();
  while (_c < '0' || '9' < _c) {
    if (_c == '-') _f = true;
    _c = getchar();
  }
  while ('0' <= _c && _c <= '9') {
    x = (x << 1) + (x << 3) + (_c & 15);
    _c = getchar();
  }
  if (_f) x = -x;
}
template <typename T>
inline void Min(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
inline void Max(T &x, T y) {
  if (x < y) x = y;
}
const int INF = 0x3f3f3f3f;
const double pi = (double)acos(-1.0);
const double eps = (double)1e-8;
const int e5 = (int)1e5 + 5;
const int MOD = (int)998244353;
inline int sig(double x) { return x < -eps ? -1 : eps < x; }
long long fac[128];
long long fp(long long a, long long n, long long mod = MOD) {
  if (n < 0) a = fp(a, mod - 2, mod), n = -n;
  long long res = 1;
  for (; n; n >>= 1, a = a * a % mod)
    if (n & 1) res = res * a % mod;
  return res;
}
struct Mint {
  int x;
  Mint() { x = 0; }
  Mint(int _x) : x(_x) {
    if (x < 0 || x >= MOD) x = (x % MOD + MOD) % MOD;
  }
  Mint(long long _x) : x(_x) {
    if (x < 0 || x >= MOD) x = (x % MOD + MOD) % MOD;
  }
  Mint operator-() const { return Mint(MOD - x); }
  Mint operator+(const Mint &rhs) const {
    return Mint(x + rhs.x >= MOD ? x + rhs.x - MOD : x + rhs.x);
  }
  Mint operator-(const Mint &rhs) const {
    return Mint(x - rhs.x < 0 ? x - rhs.x + MOD : x - rhs.x);
  }
  Mint operator*(const Mint &rhs) const {
    return Mint((long long)x * rhs.x % MOD);
  }
  Mint operator/(const Mint &rhs) const {
    return Mint(x * fp(rhs.x, -1) % MOD);
  }
  Mint &operator+=(const Mint &rhs) {
    x += rhs.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }
  Mint &operator*=(const Mint &rhs) {
    x = ((long long)x * rhs.x) % MOD;
    return *this;
  }
  bool operator==(const Mint &rhs) const { return x == rhs.x; }
  bool operator!=(const Mint &rhs) const { return x != rhs.x; }
  friend ostream &operator<<(ostream &out, const Mint &rhs) {
    return out << rhs.x;
  }
  friend istream &operator>>(istream &in, Mint &rhs) { return in >> rhs.x; }
};
const int maxn = (int)2e5 + 20;
const int maxm = (int)1e6 + 20;
const int N = 500 + 5;
struct PQ_tree {
  int n, tot;
  int fail;
  vector<int> G[N << 2];
  int ty[N << 2];
  int sz[N << 2];
  int szc[N << 2];
  bool s[N];
  inline int getstate(int u) {
    if (szc[u] == 0) return 0;
    if (szc[u] == sz[u]) return 2;
    return 1;
  }
  void addson(int x, int y) {
    if (y) G[x].push_back(y);
  }
  void join(int x, int y) {
    for (auto v : G[y]) G[x].push_back(v);
  }
  int mergeP(vector<int> &vec) {
    if (vec.size() == 0) return 0;
    if (vec.size() == 1) return vec[0];
    G[++tot] = vec;
    return tot;
  }
  void init(int _n) {
    n = _n;
    tot = n + 1;
    memset(ty, 0, sizeof(ty));
    for (int i = 1; i <= n; i++) G[n + 1].push_back(i);
    fail = 0;
  }
  void dfs(int u) {
    sz[u] = u <= n;
    szc[u] = u <= n && s[u];
    for (auto v : G[u]) {
      dfs(v);
      sz[u] += sz[v];
      szc[u] += szc[v];
    }
  }
  int check(int u, int t) {
    if (fail) return 0;
    vector<int> vec[3];
    for (auto v : G[u]) vec[getstate(v)].push_back(v);
    if (vec[1].size() > 2 || (t && vec[1].size() > 1)) return fail = 1, 0;
    if (t == 0 && vec[1].size() == 1 && vec[2].size() == 0)
      return check(vec[1][0], 0);
    if (ty[u] == 0) {
      int p2 = mergeP(vec[2]);
      if (t == 0) {
        G[u] = vec[0];
        if (vec[1].size() == 0)
          addson(u, p2);
        else {
          int tmp1 = check(vec[1][0], 2);
          addson(tmp1, p2);
          if (vec[1].size() == 2) join(tmp1, check(vec[1][1], 1));
          addson(u, tmp1);
        }
        return u;
      } else {
        ty[u] = 1;
        G[u].clear();
        addson(u, p2);
        if (vec[1].size() == 1) join(u, check(vec[1][0], 1));
        addson(u, mergeP(vec[0]));
        if (t == 2) reverse(G[u].begin(), G[u].end());
      }
      return u;
    } else {
      if (getstate(G[u].front()) > getstate(G[u].back()))
        reverse(G[u].begin(), G[u].end());
      int flag = 0;
      vector<int> tG;
      for (auto v : G[u]) {
        int sta = getstate(v);
        if (sta == 0) {
          if (flag == 1) flag = 2;
          tG.push_back(v);
        } else if (sta == 2) {
          if (flag == 0)
            flag = 1;
          else if (flag == 2)
            return fail = 2, 0;
          tG.push_back(v);
        } else {
          int p1;
          if (flag == 0)
            flag = 1, p1 = check(v, 2);
          else if (flag == 1)
            flag = 2, p1 = check(v, 1);
          else
            return fail = 3, 0;
          for (auto x : G[v]) tG.push_back(x);
        }
      }
      if (t && flag == 2) return fail = 4, 0;
      if (t == 1) reverse(tG.begin(), tG.end());
      G[u] = tG;
      return u;
    }
  }
  int res;
  void dfs_permutation(int u) {
    if (u <= n) {
      return;
    }
    if (!ty[u]) {
      res = (long long)res * fac[G[u].size()] % MOD;
    } else if (G[u].size() != 1) {
      res = (long long)res * 2 % MOD;
    }
    for (auto v : G[u]) {
      dfs_permutation(v);
    }
  }
  int get_permutation() {
    res = 1;
    dfs_permutation(n + 1);
    return res;
  }
  void restrict(vector<int> res) {
    for (int i = 1; i <= n; i++) s[i] = 0;
    for (auto x : res) s[x] = 1;
    dfs(n + 1);
    check(n + 1, 0);
  }
};
void work() {
  fac[0] = 1;
  for (int i = 1; i < 128; i++) {
    fac[i] = fac[i - 1] * i % MOD;
  }
  int n, m;
  cin >> n >> m;
  PQ_tree *pq = new PQ_tree;
  pq->init(n);
  for (int i = 0; i < m; i++) {
    vector<int> res;
    int num;
    cin >> num;
    while (num--) {
      int x;
      cin >> x;
      res.push_back(x);
    }
    pq->restrict(res);
  }
  if (pq->fail) {
    cout << 0 << endl;
  } else {
    cout << pq->get_permutation() << endl;
  }
  delete pq;
}
int main(int argc, char **argv) {
  int tc = 1;
  for (int ca = 1; ca <= tc; ca++) {
    work();
  }
  return 0;
}
