For a permutation p of numbers 1 through n, we define a stair array a as follows: a_i is length of the longest segment of permutation which contains position i and is made of consecutive values in sorted order: [x, x+1, …, y-1, y] or [y, y-1, …, x+1, x] for some x ≤ y. For example, for permutation p = [4, 1, 2, 3, 7, 6, 5] we have a = [1, 3, 3, 3, 3, 3, 3]. 

You are given the stair array a. Your task is to calculate the number of permutations which have stair array equal to a. Since the number can be big, compute it modulo 998 244 353. Note that this number can be equal to zero.

Input

The first line of input contains integer n (1 ≤ n ≤ 10^5) — the length of a stair array a.

The second line of input contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).

Output

Print the number of permutations which have stair array equal to a. Since the number can be big, compute it modulo 998 244 353.

Examples

Input


6
3 3 3 1 1 1


Output


6


Input


7
4 4 4 4 3 3 3


Output


6


Input


1
1


Output


1


Input


8
2 2 2 2 2 2 1 1


Output


370


Input


4
3 2 3 1


Output


0
#include <bits/stdc++.h>
using namespace std;
long long get_time() {
  return chrono::duration_cast<chrono::nanoseconds>(
             chrono::steady_clock::now().time_since_epoch())
      .count();
}
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
  bool done_something = false;
  stringstream res;
  res << "[";
  for (; begin_iter != end_iter and counter; ++begin_iter) {
    done_something = true;
    counter--;
    res << *begin_iter << ", ";
  }
  string str = res.str();
  if (done_something) {
    str.pop_back();
    str.pop_back();
  }
  str += "]";
  return str;
}
template <typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T>& p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    out << v[i];
    if (i != (int)v.size() - 1) out << ", ";
  }
  out << "]";
  return out;
}
template <class TH>
void _dbg(const char* name, TH val) {
  clog << name << ": " << val << endl;
}
template <class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
  while (*names != ',') clog << *names++;
  clog << ": " << curr_val << ", ";
  _dbg(names + 1, vals...);
}
const long long mod = 998244353;
const int MAXN = 100;
const int MAXM = 100;
int N;
bool visited[MAXM];
vector<int> aa[MAXM];
int M;
bitset<MAXN> S[MAXM];
bool dfs(int v, vector<bitset<MAXN>>& E) {
  visited[v] = true;
  string intersection_type(E.size(), '-');
  bitset<MAXN> A = S[v];
  for (int i = 0; i < ((int)((E).size())); i++) {
    bitset<MAXN> inter = A & E[i];
    if (inter.none())
      intersection_type[i] = '0';
    else if (inter != E[i])
      intersection_type[i] = '1';
    else
      intersection_type[i] = '2';
    A = A & ~inter;
  }
  bool is_prefix = regex_match(intersection_type, regex("2*1?0*"));
  bool is_suffix = regex_match(intersection_type, regex("0*1?2*"));
  bool is_interval = regex_match(intersection_type, regex("0*1?2*1?0*"));
  if (!is_interval) return false;
  if (!is_prefix and !is_suffix and A.any()) return false;
  if (!is_suffix and A.any()) {
    reverse(E.begin(), E.end());
    reverse(intersection_type.begin(), intersection_type.end());
  }
  if (A.any()) {
    E.push_back(A);
    intersection_type += '2';
  }
  for (int i = ((int)((E).size())) - 1; i >= 0; i--) {
    if (intersection_type[i] == '1') {
      bitset<MAXN> e1 = S[v] & E[i];
      bitset<MAXN> e2 = E[i] & ~S[v];
      E.erase(E.begin() + i);
      if (i >= 1 and intersection_type[i - 1] != '0') {
        E.insert(E.begin() + i, e2);
        E.insert(E.begin() + i, e1);
      } else if (i < ((int)((intersection_type).size())) - 1 and
                 intersection_type[i + 1] != '0') {
        E.insert(E.begin() + i, e1);
        E.insert(E.begin() + i, e2);
      } else
        assert(0);
    }
  }
  for (int a : aa[v]) {
    if (visited[a]) continue;
    if (!dfs(a, E)) return false;
  }
  return true;
}
long long solve() {
  for (int i = 0; i < M; i++) aa[i].clear(), visited[i] = false;
  for (int i = 0; i < M; i++) {
    for (int j = i + 1; j < M; j++) {
      bitset<MAXN> inter = S[i] & S[j];
      if (inter.any() and inter != S[i] and inter != S[j]) {
        aa[i].push_back(j);
        aa[j].push_back(i);
      }
    }
  }
  vector<pair<bitset<MAXN>, vector<bitset<MAXN>>>> equiv;
  for (int i = 0; i < M; i++) {
    if (visited[i]) continue;
    vector<bitset<MAXN>> E;
    if (!dfs(i, E)) return 0;
    bitset<MAXN> PP;
    for (auto e : E) PP |= e;
    equiv.push_back({PP, E});
  }
  bitset<MAXN> full_set;
  for (int i = 0; i < N; i++) full_set[i] = 1;
  equiv.emplace_back(full_set, vector<bitset<MAXN>>{full_set});
  sort(equiv.begin(), equiv.end(),
       [&](const pair<bitset<MAXN>, vector<bitset<MAXN>>>& A,
           const pair<bitset<MAXN>, vector<bitset<MAXN>>>& B) {
         if (A.first.count() != B.first.count())
           return A.first.count() > B.first.count();
         return A.second.size() < B.second.size();
       });
  long long res = 1;
  for (int i = 0; i < ((int)((equiv).size())); i++) {
    if (equiv[i].second.size() >= 2) res *= 2;
    for (bitset<MAXN> A : equiv[i].second) {
      int cnt = A.count();
      for (int j = i + 1; j < ((int)((equiv).size())); j++) {
        bitset<MAXN> P = equiv[j].first;
        if ((P & A) == P) {
          cnt -= P.count() - 1;
          A &= ~P;
        }
      }
      for (int m = 1; m <= cnt; m++) res = res * m % mod;
    }
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int q;
    cin >> q;
    for (int j = 0; j < q; j++) {
      int s;
      cin >> s;
      S[i][s - 1] = 1;
    }
  }
  cout << solve() << "\n";
}
