#include <bits/stdc++.h>
using namespace std;
template <typename T>
T power(T a, long long b) {
  T r = 1;
  while (b) {
    if (b & 1) {
      r *= a;
    }
    a *= a;
    b >>= 1;
  }
  return r;
}
template <typename T>
T inverse(T a, T m) {
  a %= m;
  if (a < 0) {
    a += m;
  }
  T b = m, u = 0, v = 1;
  while (a) {
    T t = b / a;
    b -= a * t;
    swap(a, b);
    u -= v * t;
    swap(u, v);
  }
  if (u < 0) {
    u += m;
  }
  return u;
}
template <int _P>
struct modnum {
  static constexpr int P = _P;

 private:
  int v;

 public:
  modnum() : v(0) {}
  modnum(long long _v) {
    v = _v % P;
    if (v < 0) {
      v += P;
    }
  }
  explicit operator int() const { return v; }
  bool operator==(const modnum& o) const { return v == o.v; }
  bool operator!=(const modnum& o) const { return v != o.v; }
  modnum inverse() const { return modnum(::inverse(v, P)); }
  modnum operator-() const { return modnum(v ? P - v : 0); }
  modnum operator+() const { return *this; }
  modnum& operator++() {
    v++;
    if (v == P) {
      v = 0;
    }
    return *this;
  }
  modnum& operator--() {
    if (v == 0) {
      v = P;
    }
    v--;
    return *this;
  }
  modnum operator++(int) {
    modnum r = *this;
    ++*this;
    return r;
  }
  modnum operator--(int) {
    modnum r = *this;
    --*this;
    return r;
  }
  modnum& operator+=(const modnum& o) {
    v += o.v;
    if (v >= P) {
      v -= P;
    }
    return *this;
  }
  modnum operator+(const modnum& o) const { return modnum(*this) += o; }
  modnum& operator-=(const modnum& o) {
    v -= o.v;
    if (v < 0) {
      v += P;
    }
    return *this;
  }
  modnum operator-(const modnum& o) const { return modnum(*this) -= o; }
  modnum& operator*=(const modnum& o) {
    v = (int)((long long)v * o.v % P);
    return *this;
  }
  modnum operator*(const modnum& o) const { return modnum(*this) *= o; }
  modnum& operator/=(const modnum& o) { return *this *= o.inverse(); }
  modnum operator/(const modnum& o) const { return modnum(*this) /= o; }
};
template <int _P>
ostream& operator<<(ostream& out, const modnum<_P>& n) {
  return out << int(n);
}
template <int _P>
istream& operator>>(istream& in, modnum<_P>& n) {
  long long _v;
  in >> _v;
  n = modnum<_P>(_v);
  return in;
}
using num = modnum<998244353>;
num ways = 1;
struct PQtree {
  int type, father;
  vector<int> child;
} t[2010];
int n, pd[2010], w[2010], size[2010], in[5010], B[2010],
    W[3] = {0, 2, 1}, ans[2010], C[600][600], len, kk;
vector<int> rem, A;
char getin() {
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  return ch;
}
int getnext() {
  int k1 = rem[(rem.size()) - 1];
  rem.pop_back();
  t[k1].child.clear();
  t[k1].type = 0;
  t[k1].father = 0;
  return k1;
}
void reverse(int k) {
  vector<int> k1;
  for (int i = 0; i < t[k].child.size(); i++) k1.push_back(t[k].child[i]);
  t[k].child.clear();
  for (int i = (k1.size()) - 1; i >= 0; i--) t[k].child.push_back(k1[i]);
}
void change(int k1, int k2, int k3) {
  if (k1 == 0) return;
  for (int i = 0; i < t[k1].child.size(); i++)
    if (t[k1].child[i] == k2) {
      t[k1].child[i] = k3;
      return;
    }
}
int reduce() {
  memset(B, 0x00, sizeof B);
  memset(size, 0x00, sizeof size);
  memset(w, 0x00, sizeof w);
  memset(pd, 0xff, sizeof pd);
  queue<int> Q;
  for (int i = 1; i <= n; i++) {
    Q.push(i);
    pd[i] = in[i];
    w[i] = in[i];
  }
  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();
    int flag = 0;
    if (w[k] == A.size()) flag = 1;
    if (pd[k] == 2) {
      vector<int> C[3];
      for (int i = 0; i < t[k].child.size(); i++) {
        int j = t[k].child[i];
        C[pd[j]].push_back(j);
      }
      if (t[k].type == 1) {
        if (C[2].size() == 0) {
          if (flag == 1) {
            if (C[1].size() > 1) {
              int k1 = getnext();
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
              t[k1].father = k;
              t[k].child.clear();
              t[k1].type = 1;
              pd[k1] = 1;
              for (int i = 0; i < C[0].size(); i++)
                t[k].child.push_back(C[0][i]);
              t[k].child.push_back(k1);
            }
          } else {
            t[k].type = 2;
            t[k].child.clear();
            if (C[0].size() > 1) {
              int k1 = getnext();
              t[k1].father = k;
              t[k].child.push_back(k1);
              t[k1].type = 1;
              pd[k1] = 0;
              for (int i = 0; i < C[0].size(); i++) {
                t[k1].child.push_back(C[0][i]);
                t[C[0][i]].father = k1;
              }
            } else if (C[0].size())
              t[k].child.push_back(C[0][0]);
            if (C[1].size() > 1) {
              int k1 = getnext();
              t[k1].father = k;
              t[k].child.push_back(k1);
              t[k1].type = 1;
              pd[k1] = 1;
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
            } else if (C[1].size())
              t[k].child.push_back(C[1][0]);
          }
        } else if (C[2].size() == 1) {
          if (flag == 1) {
            t[k].child.clear();
            if (C[1].size() == 1) {
              t[C[2][0]].child.push_back(C[1][0]);
              t[C[1][0]].father = C[2][0];
              for (int i = 0; i < C[0].size(); i++)
                t[k].child.push_back(C[0][i]);
              t[k].child.push_back(C[2][0]);
            } else if (C[1].size()) {
              int k1 = getnext(), k2 = C[2][0];
              t[k1].type = 1;
              t[k1].father = k2;
              pd[k1] = 1;
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
              t[k2].child.push_back(k1);
              for (int i = 0; i < C[0].size(); i++)
                t[k].child.push_back(C[0][i]);
              t[k].child.push_back(k2);
            }
            if (t[k].child.size() == 1) {
              t[t[k].child[0]].father = t[k].father;
              change(t[k].father, k, t[k].child[0]);
              rem.push_back(k);
            }
          } else {
            t[k].child.clear();
            t[k].type = 2;
            if (C[0].size() == 1)
              t[k].child.push_back(C[0][0]);
            else if (C[0].size()) {
              int k1 = getnext();
              t[k1].type = 1;
              t[k1].father = k;
              pd[k1] = 0;
              for (int i = 0; i < C[0].size(); i++) {
                t[k1].child.push_back(C[0][i]);
                t[C[0][i]].father = k1;
              }
              t[k].child.push_back(k1);
            }
            int k2 = C[2][0];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            if (C[1].size() == 1)
              t[k].child.push_back(C[1][0]);
            else if (C[1].size()) {
              int k1 = getnext();
              t[k1].type = 1;
              t[k1].father = k;
              pd[k1] = 1;
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
              t[k].child.push_back(k1);
            }
            rem.push_back(k2);
          }
        } else if (C[2].size() == 2) {
          if (flag == 0) return 0;
          t[k].child.clear();
          for (int i = 0; i < C[0].size(); i++) t[k].child.push_back(C[0][i]);
          int k1 = getnext();
          int k2 = C[2][0];
          t[k1].type = 2;
          t[k1].father = k;
          for (int i = 0; i < t[k2].child.size(); i++) {
            t[k1].child.push_back(t[k2].child[i]);
            t[t[k2].child[i]].father = k1;
          }
          rem.push_back(k2);
          pd[k1] = 2;
          if (C[1].size() == 1) {
            t[k1].child.push_back(C[1][0]);
            t[C[1][0]].father = k1;
          } else if (C[1].size()) {
            int k3 = getnext();
            t[k3].type = 1;
            t[k3].father = k1;
            pd[k3] = 1;
            for (int i = 0; i < C[1].size(); i++) {
              t[k3].child.push_back(C[1][i]);
              t[C[1][i]].father = k3;
            }
            t[k1].child.push_back(k3);
          }
          t[k].child.push_back(k1);
          k2 = C[2][1];
          for (int i = (t[k2].child.size()) - 1; i >= 0; i--) {
            t[k1].child.push_back(t[k2].child[i]);
            t[t[k2].child[i]].father = k1;
          }
          rem.push_back(k2);
          if (t[k].child.size() == 1) {
            t[k1].father = t[k].father;
            change(t[k].father, k, k1);
            rem.push_back(k);
          }
        } else
          return 0;
      } else {
        int now = 0, flag2 = 0;
        for (int i = 0; i < t[k].child.size(); i++) {
          int j = t[k].child[i];
          if (W[pd[j]] < now) {
            flag2 = 1;
            break;
          }
          now = W[pd[j]];
        }
        int flag3 = 0;
        now = 2;
        for (int i = 0; i < t[k].child.size(); i++) {
          int j = t[k].child[i];
          if (W[pd[j]] > now) {
            flag3 = 1;
            break;
          }
          now = W[pd[j]];
        }
        if ((flag2 == 0 || flag3 == 0) && C[2].size() == 1) {
          if (flag3 == 0) {
            reverse(k);
            C[0].clear();
            C[1].clear();
            C[2].clear();
            for (int i = 0; i < t[k].child.size(); i++) {
              int j = t[k].child[i];
              C[pd[j]].push_back(j);
            }
          }
          t[k].child.clear();
          for (int i = 0; i < C[0].size(); i++) t[k].child.push_back(C[0][i]);
          int k2 = C[2][0];
          for (int i = 0; i < t[k2].child.size(); i++) {
            t[k].child.push_back(t[k2].child[i]);
            t[t[k2].child[i]].father = k;
          }
          rem.push_back(k2);
          for (int i = 0; i < C[1].size(); i++) t[k].child.push_back(C[1][i]);
        } else if (C[2].size() <= 2 && C[2].size() >= 1) {
          if (flag == 0) return 0;
          int two1 = -1, two2 = -1;
          for (int i = 0; i < t[k].child.size(); i++) {
            int j = t[k].child[i];
            if (pd[j] == 2) {
              if (two1 != -1)
                two2 = i;
              else
                two1 = i;
            }
          }
          if (C[2].size() == 2) {
            for (int i = 0; i < two1; i++) {
              int j = t[k].child[i];
              if (pd[j] != 0) return 0;
            }
            for (int i = two1 + 1; i < two2; i++) {
              int j = t[k].child[i];
              if (pd[j] != 1) return 0;
            }
            for (int i = two2 + 1; i < t[k].child.size(); i++) {
              int j = t[k].child[i];
              if (pd[j] != 0) return 0;
            }
            reverse(C[2][1]);
            t[k].child.clear();
            for (int i = 0; i < two1; i++) t[k].child.push_back(C[0][i]);
            int k2 = C[2][0];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            rem.push_back(k2);
            for (int i = 0; i < C[1].size(); i++) t[k].child.push_back(C[1][i]);
            k2 = C[2][1];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            rem.push_back(k2);
            for (int i = two1; i < C[0].size(); i++)
              t[k].child.push_back(C[0][i]);
          } else {
            int flag4 = 0;
            for (int i = 0; i < two1; i++) {
              int k1 = t[k].child[i];
              if (pd[k1] == 1) {
                flag4 = 1;
                break;
              }
            }
            if (flag4) {
              reverse(k);
              two1 = (t[k].child.size()) - two1 - 1;
            }
            for (int i = 0; i < two1; i++) {
              int k1 = t[k].child[i];
              if (pd[k1]) return 0;
            }
            int now = 1;
            for (int i = two1 + 1; i < t[k].child.size(); i++) {
              int k1 = t[k].child[i];
              if (pd[k1] > now) return 0;
              now = pd[k1];
            }
            C[0].clear();
            C[1].clear();
            C[2].clear();
            for (int i = 0; i < t[k].child.size(); i++) {
              int j = t[k].child[i];
              C[pd[j]].push_back(j);
            }
            t[k].child.clear();
            for (int i = 0; i < two1; i++) t[k].child.push_back(C[0][i]);
            int k2 = C[2][0];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            rem.push_back(k2);
            for (int i = 0; i < C[1].size(); i++) t[k].child.push_back(C[1][i]);
            for (int i = two1; i < C[0].size(); i++)
              t[k].child.push_back(C[0][i]);
          }
        } else if (C[2].size() == 0) {
          if (pd[t[k].child[0]] == 1) reverse(k);
          int k1 = t[k].child.size();
          for (int i = 0; i < t[k].child.size(); i++) {
            int k2 = t[k].child[i];
            if (pd[k2] == 1) {
              k1 = i;
              break;
            }
          }
          int k3 = t[k].child.size();
          for (int i = k1; i < t[k].child.size(); i++) {
            int k2 = t[k].child[i];
            if (pd[k2] == 0) {
              k3 = i;
              break;
            }
          }
          if (flag == 0 && k3 != t[k].child.size()) return 0;
          if (flag == 1)
            for (int i = k3; i < t[k].child.size(); i++) {
              int k2 = t[k].child[i];
              if (pd[k2] == 1) return 0;
            }
        } else
          return 0;
      }
    }
    if (flag) return 1;
    int k1 = t[k].father;
    size[k1]++;
    w[k1] += w[k];
    if (pd[k1] == -1)
      pd[k1] = pd[k];
    else if (pd[k1] != pd[k])
      pd[k1] = 2;
    if (size[k1] == t[k1].child.size()) Q.push(k1);
  }
}
void print(int k) {
  if (t[k].type == 0) {
    ans[++len] = k;
    return;
  }
  if (t[k].type == 1) {
    for (int i = 1; i <= t[k].child.size(); i++) {
      ways *= i;
    }
  } else {
    ways *= 2;
  }
  for (int i = 0; i < t[k].child.size(); i++) print(t[k].child[i]);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    t[i].type = 0;
    t[i].father = n + 1;
    t[i].child.clear();
    t[n + 1].child.push_back(i);
  }
  t[n + 1].type = 1;
  for (int i = 2000; i > n + 1; i--) rem.push_back(i);
  for (int i = 1; i <= m; i++) {
    memset(in, 0x00, sizeof in);
    A.clear();
    int sz;
    scanf("%d", &sz);
    while (sz--) {
      int p;
      scanf("%d", &p);
      A.push_back(p);
      in[p] = 1;
    }
    kk = i;
    if (reduce() == 0) {
      cout << 0 << endl;
      return 0;
    }
  }
  int root = 1;
  while (t[root].father) root = t[root].father;
  print(root);
  cout << ways << endl;
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T power(T a, long long b) {
  T r = 1;
  while (b) {
    if (b & 1) {
      r *= a;
    }
    a *= a;
    b >>= 1;
  }
  return r;
}
template <typename T>
T inverse(T a, T m) {
  a %= m;
  if (a < 0) {
    a += m;
  }
  T b = m, u = 0, v = 1;
  while (a) {
    T t = b / a;
    b -= a * t;
    swap(a, b);
    u -= v * t;
    swap(u, v);
  }
  if (u < 0) {
    u += m;
  }
  return u;
}
template <int _P>
struct modnum {
  static constexpr int P = _P;

 private:
  int v;

 public:
  modnum() : v(0) {}
  modnum(long long _v) {
    v = _v % P;
    if (v < 0) {
      v += P;
    }
  }
  explicit operator int() const { return v; }
  bool operator==(const modnum& o) const { return v == o.v; }
  bool operator!=(const modnum& o) const { return v != o.v; }
  modnum inverse() const { return modnum(::inverse(v, P)); }
  modnum operator-() const { return modnum(v ? P - v : 0); }
  modnum operator+() const { return *this; }
  modnum& operator++() {
    v++;
    if (v == P) {
      v = 0;
    }
    return *this;
  }
  modnum& operator--() {
    if (v == 0) {
      v = P;
    }
    v--;
    return *this;
  }
  modnum operator++(int) {
    modnum r = *this;
    ++*this;
    return r;
  }
  modnum operator--(int) {
    modnum r = *this;
    --*this;
    return r;
  }
  modnum& operator+=(const modnum& o) {
    v += o.v;
    if (v >= P) {
      v -= P;
    }
    return *this;
  }
  modnum operator+(const modnum& o) const { return modnum(*this) += o; }
  modnum& operator-=(const modnum& o) {
    v -= o.v;
    if (v < 0) {
      v += P;
    }
    return *this;
  }
  modnum operator-(const modnum& o) const { return modnum(*this) -= o; }
  modnum& operator*=(const modnum& o) {
    v = (int)((long long)v * o.v % P);
    return *this;
  }
  modnum operator*(const modnum& o) const { return modnum(*this) *= o; }
  modnum& operator/=(const modnum& o) { return *this *= o.inverse(); }
  modnum operator/(const modnum& o) const { return modnum(*this) /= o; }
};
template <int _P>
ostream& operator<<(ostream& out, const modnum<_P>& n) {
  return out << int(n);
}
template <int _P>
istream& operator>>(istream& in, modnum<_P>& n) {
  long long _v;
  in >> _v;
  n = modnum<_P>(_v);
  return in;
}
using num = modnum<998244353>;
num ways = 1;
struct PQtree {
  int type, father;
  vector<int> child;
} t[2010];
int n, pd[2010], w[2010], size[2010], in[5010], B[2010],
    W[3] = {0, 2, 1}, ans[2010], C[600][600], len, kk;
vector<int> rem, A;
char getin() {
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  return ch;
}
int getnext() {
  int k1 = rem[(rem.size()) - 1];
  rem.pop_back();
  t[k1].child.clear();
  t[k1].type = 0;
  t[k1].father = 0;
  return k1;
}
void reverse(int k) {
  vector<int> k1;
  for (int i = 0; i < t[k].child.size(); i++) k1.push_back(t[k].child[i]);
  t[k].child.clear();
  for (int i = (k1.size()) - 1; i >= 0; i--) t[k].child.push_back(k1[i]);
}
void change(int k1, int k2, int k3) {
  if (k1 == 0) return;
  for (int i = 0; i < t[k1].child.size(); i++)
    if (t[k1].child[i] == k2) {
      t[k1].child[i] = k3;
      return;
    }
}
int reduce() {
  memset(B, 0x00, sizeof B);
  memset(size, 0x00, sizeof size);
  memset(w, 0x00, sizeof w);
  memset(pd, 0xff, sizeof pd);
  queue<int> Q;
  for (int i = 1; i <= n; i++) {
    Q.push(i);
    pd[i] = in[i];
    w[i] = in[i];
  }
  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();
    int flag = 0;
    if (w[k] == A.size()) flag = 1;
    if (pd[k] == 2) {
      vector<int> C[3];
      for (int i = 0; i < t[k].child.size(); i++) {
        int j = t[k].child[i];
        C[pd[j]].push_back(j);
      }
      if (t[k].type == 1) {
        if (C[2].size() == 0) {
          if (flag == 1) {
            if (C[1].size() > 1) {
              int k1 = getnext();
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
              t[k1].father = k;
              t[k].child.clear();
              t[k1].type = 1;
              pd[k1] = 1;
              for (int i = 0; i < C[0].size(); i++)
                t[k].child.push_back(C[0][i]);
              t[k].child.push_back(k1);
            }
          } else {
            t[k].type = 2;
            t[k].child.clear();
            if (C[0].size() > 1) {
              int k1 = getnext();
              t[k1].father = k;
              t[k].child.push_back(k1);
              t[k1].type = 1;
              pd[k1] = 0;
              for (int i = 0; i < C[0].size(); i++) {
                t[k1].child.push_back(C[0][i]);
                t[C[0][i]].father = k1;
              }
            } else if (C[0].size())
              t[k].child.push_back(C[0][0]);
            if (C[1].size() > 1) {
              int k1 = getnext();
              t[k1].father = k;
              t[k].child.push_back(k1);
              t[k1].type = 1;
              pd[k1] = 1;
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
            } else if (C[1].size())
              t[k].child.push_back(C[1][0]);
          }
        } else if (C[2].size() == 1) {
          if (flag == 1) {
            t[k].child.clear();
            if (C[1].size() == 1) {
              t[C[2][0]].child.push_back(C[1][0]);
              t[C[1][0]].father = C[2][0];
              for (int i = 0; i < C[0].size(); i++)
                t[k].child.push_back(C[0][i]);
              t[k].child.push_back(C[2][0]);
            } else if (C[1].size()) {
              int k1 = getnext(), k2 = C[2][0];
              t[k1].type = 1;
              t[k1].father = k2;
              pd[k1] = 1;
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
              t[k2].child.push_back(k1);
              for (int i = 0; i < C[0].size(); i++)
                t[k].child.push_back(C[0][i]);
              t[k].child.push_back(k2);
            }
            if (t[k].child.size() == 1) {
              t[t[k].child[0]].father = t[k].father;
              change(t[k].father, k, t[k].child[0]);
              rem.push_back(k);
            }
          } else {
            t[k].child.clear();
            t[k].type = 2;
            if (C[0].size() == 1)
              t[k].child.push_back(C[0][0]);
            else if (C[0].size()) {
              int k1 = getnext();
              t[k1].type = 1;
              t[k1].father = k;
              pd[k1] = 0;
              for (int i = 0; i < C[0].size(); i++) {
                t[k1].child.push_back(C[0][i]);
                t[C[0][i]].father = k1;
              }
              t[k].child.push_back(k1);
            }
            int k2 = C[2][0];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            if (C[1].size() == 1)
              t[k].child.push_back(C[1][0]);
            else if (C[1].size()) {
              int k1 = getnext();
              t[k1].type = 1;
              t[k1].father = k;
              pd[k1] = 1;
              for (int i = 0; i < C[1].size(); i++) {
                t[k1].child.push_back(C[1][i]);
                t[C[1][i]].father = k1;
              }
              t[k].child.push_back(k1);
            }
            rem.push_back(k2);
          }
        } else if (C[2].size() == 2) {
          if (flag == 0) return 0;
          t[k].child.clear();
          for (int i = 0; i < C[0].size(); i++) t[k].child.push_back(C[0][i]);
          int k1 = getnext();
          int k2 = C[2][0];
          t[k1].type = 2;
          t[k1].father = k;
          for (int i = 0; i < t[k2].child.size(); i++) {
            t[k1].child.push_back(t[k2].child[i]);
            t[t[k2].child[i]].father = k1;
          }
          rem.push_back(k2);
          pd[k1] = 2;
          if (C[1].size() == 1) {
            t[k1].child.push_back(C[1][0]);
            t[C[1][0]].father = k1;
          } else if (C[1].size()) {
            int k3 = getnext();
            t[k3].type = 1;
            t[k3].father = k1;
            pd[k3] = 1;
            for (int i = 0; i < C[1].size(); i++) {
              t[k3].child.push_back(C[1][i]);
              t[C[1][i]].father = k3;
            }
            t[k1].child.push_back(k3);
          }
          t[k].child.push_back(k1);
          k2 = C[2][1];
          for (int i = (t[k2].child.size()) - 1; i >= 0; i--) {
            t[k1].child.push_back(t[k2].child[i]);
            t[t[k2].child[i]].father = k1;
          }
          rem.push_back(k2);
          if (t[k].child.size() == 1) {
            t[k1].father = t[k].father;
            change(t[k].father, k, k1);
            rem.push_back(k);
          }
        } else
          return 0;
      } else {
        int now = 0, flag2 = 0;
        for (int i = 0; i < t[k].child.size(); i++) {
          int j = t[k].child[i];
          if (W[pd[j]] < now) {
            flag2 = 1;
            break;
          }
          now = W[pd[j]];
        }
        int flag3 = 0;
        now = 2;
        for (int i = 0; i < t[k].child.size(); i++) {
          int j = t[k].child[i];
          if (W[pd[j]] > now) {
            flag3 = 1;
            break;
          }
          now = W[pd[j]];
        }
        if ((flag2 == 0 || flag3 == 0) && C[2].size() == 1) {
          if (flag3 == 0) {
            reverse(k);
            C[0].clear();
            C[1].clear();
            C[2].clear();
            for (int i = 0; i < t[k].child.size(); i++) {
              int j = t[k].child[i];
              C[pd[j]].push_back(j);
            }
          }
          t[k].child.clear();
          for (int i = 0; i < C[0].size(); i++) t[k].child.push_back(C[0][i]);
          int k2 = C[2][0];
          for (int i = 0; i < t[k2].child.size(); i++) {
            t[k].child.push_back(t[k2].child[i]);
            t[t[k2].child[i]].father = k;
          }
          rem.push_back(k2);
          for (int i = 0; i < C[1].size(); i++) t[k].child.push_back(C[1][i]);
        } else if (C[2].size() <= 2 && C[2].size() >= 1) {
          if (flag == 0) return 0;
          int two1 = -1, two2 = -1;
          for (int i = 0; i < t[k].child.size(); i++) {
            int j = t[k].child[i];
            if (pd[j] == 2) {
              if (two1 != -1)
                two2 = i;
              else
                two1 = i;
            }
          }
          if (C[2].size() == 2) {
            for (int i = 0; i < two1; i++) {
              int j = t[k].child[i];
              if (pd[j] != 0) return 0;
            }
            for (int i = two1 + 1; i < two2; i++) {
              int j = t[k].child[i];
              if (pd[j] != 1) return 0;
            }
            for (int i = two2 + 1; i < t[k].child.size(); i++) {
              int j = t[k].child[i];
              if (pd[j] != 0) return 0;
            }
            reverse(C[2][1]);
            t[k].child.clear();
            for (int i = 0; i < two1; i++) t[k].child.push_back(C[0][i]);
            int k2 = C[2][0];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            rem.push_back(k2);
            for (int i = 0; i < C[1].size(); i++) t[k].child.push_back(C[1][i]);
            k2 = C[2][1];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            rem.push_back(k2);
            for (int i = two1; i < C[0].size(); i++)
              t[k].child.push_back(C[0][i]);
          } else {
            int flag4 = 0;
            for (int i = 0; i < two1; i++) {
              int k1 = t[k].child[i];
              if (pd[k1] == 1) {
                flag4 = 1;
                break;
              }
            }
            if (flag4) {
              reverse(k);
              two1 = (t[k].child.size()) - two1 - 1;
            }
            for (int i = 0; i < two1; i++) {
              int k1 = t[k].child[i];
              if (pd[k1]) return 0;
            }
            int now = 1;
            for (int i = two1 + 1; i < t[k].child.size(); i++) {
              int k1 = t[k].child[i];
              if (pd[k1] > now) return 0;
              now = pd[k1];
            }
            C[0].clear();
            C[1].clear();
            C[2].clear();
            for (int i = 0; i < t[k].child.size(); i++) {
              int j = t[k].child[i];
              C[pd[j]].push_back(j);
            }
            t[k].child.clear();
            for (int i = 0; i < two1; i++) t[k].child.push_back(C[0][i]);
            int k2 = C[2][0];
            for (int i = 0; i < t[k2].child.size(); i++) {
              t[k].child.push_back(t[k2].child[i]);
              t[t[k2].child[i]].father = k;
            }
            rem.push_back(k2);
            for (int i = 0; i < C[1].size(); i++) t[k].child.push_back(C[1][i]);
            for (int i = two1; i < C[0].size(); i++)
              t[k].child.push_back(C[0][i]);
          }
        } else if (C[2].size() == 0) {
          if (pd[t[k].child[0]] == 1) reverse(k);
          int k1 = t[k].child.size();
          for (int i = 0; i < t[k].child.size(); i++) {
            int k2 = t[k].child[i];
            if (pd[k2] == 1) {
              k1 = i;
              break;
            }
          }
          int k3 = t[k].child.size();
          for (int i = k1; i < t[k].child.size(); i++) {
            int k2 = t[k].child[i];
            if (pd[k2] == 0) {
              k3 = i;
              break;
            }
          }
          if (flag == 0 && k3 != t[k].child.size()) return 0;
          if (flag == 1)
            for (int i = k3; i < t[k].child.size(); i++) {
              int k2 = t[k].child[i];
              if (pd[k2] == 1) return 0;
            }
        } else
          return 0;
      }
    }
    if (flag) return 1;
    int k1 = t[k].father;
    size[k1]++;
    w[k1] += w[k];
    if (pd[k1] == -1)
      pd[k1] = pd[k];
    else if (pd[k1] != pd[k])
      pd[k1] = 2;
    if (size[k1] == t[k1].child.size()) Q.push(k1);
  }
}
void print(int k) {
  if (t[k].type == 0) {
    ans[++len] = k;
    return;
  }
  if (t[k].type == 1) {
    for (int i = 1; i <= t[k].child.size(); i++) {
      ways *= i;
    }
  } else {
    ways *= 2;
  }
  for (int i = 0; i < t[k].child.size(); i++) print(t[k].child[i]);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    t[i].type = 0;
    t[i].father = n + 1;
    t[i].child.clear();
    t[n + 1].child.push_back(i);
  }
  t[n + 1].type = 1;
  for (int i = 2000; i > n + 1; i--) rem.push_back(i);
  for (int i = 1; i <= m; i++) {
    memset(in, 0x00, sizeof in);
    A.clear();
    int sz;
    scanf("%d", &sz);
    while (sz--) {
      int p;
      scanf("%d", &p);
      A.push_back(p);
      in[p] = 1;
    }
    kk = i;
    if (reduce() == 0) {
      cout << 0 << endl;
      return 0;
    }
  }
  int root = 1;
  while (t[root].father) root = t[root].father;
  print(root);
  cout << ways << endl;
  return 0;
}

```