Problem: This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of m and the time limit. You need to solve both subtasks in order to hack this one.

There are n+1 distinct colours in the universe, numbered 0 through n. There is a strip of paper m centimetres long initially painted with colour 0. 

Alice took a brush and painted the strip using the following process. For each i from 1 to n, in this order, she picks two integers 0 ≤ a_i < b_i ≤ m, such that the segment [a_i, b_i] is currently painted with a single colour, and repaints it with colour i. 

Alice chose the segments in such a way that each centimetre is now painted in some colour other than 0. Formally, the segment [i-1, i] is painted with colour c_i (c_i ≠ 0). Every colour other than 0 is visible on the strip.

Count the number of different pairs of sequences \\{a_i\}_{i=1}^n, \\{b_i\}_{i=1}^n that result in this configuration. 

Since this number may be large, output it modulo 998244353.

Input

The first line contains a two integers n, m (1 ≤ n ≤ 500, n = m) — the number of colours excluding the colour 0 and the length of the paper, respectively.

The second line contains m space separated integers c_1, c_2, …, c_m (1 ≤ c_i ≤ n) — the colour visible on the segment [i-1, i] after the process ends. It is guaranteed that for all j between 1 and n there is an index k such that c_k = j.

Note that since in this subtask n = m, this means that c is a permutation of integers 1 through n.

Output

Output a single integer — the number of ways Alice can perform the painting, modulo 998244353.

Examples

Input


3 3
1 2 3


Output


5


Input


7 7
4 5 1 6 2 3 7


Output


165

Note

In the first example, there are 5 ways, all depicted in the figure below. Here, 0 is white, 1 is red, 2 is green and 3 is blue.

<image>

Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour 2.

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 514;
int c[SIZE];
long long dp[SIZE][SIZE];
long long solve(vector<int> tmp) {
  int n = ((int)(tmp).size());
  for (int i = (1); i <= (n); ++i) c[i] = tmp[i - 1];
  sort((tmp).begin(), (tmp).end());
  for (int i = (1); i <= (n); ++i)
    c[i] = (lower_bound(tmp.begin(), tmp.end(), c[i]) - tmp.begin()) + 1;
  for (int i = (1); i <= (n + 1); ++i) dp[i][i - 1] = 1;
  for (int i = (0); i <= (n - 1); ++i) {
    for (int ll = (1); ll <= (n - i); ++ll) {
      int rr = ll + i;
      pair<int, int> mi{n + 1, -1};
      for (int k = (ll); k <= (rr); ++k) {
        mi = min(mi, {c[k], k});
      }
      int id = mi.second;
      long long vl = 0, vr = 0;
      for (int k = (ll); k <= (id); ++k) ADD(vl, dp[ll][k - 1] * dp[k][id - 1]);
      for (int k = (id); k <= (rr); ++k) ADD(vr, dp[id + 1][k] * dp[k + 1][rr]);
      dp[ll][rr] = vl * vr % MOD;
    }
  }
  return dp[1][n];
}
int input[1000010];
int cnt[SIZE];
vector<pair<int, int> > AA[SIZE];
int lt[SIZE];
struct BIT {
  int _n;
  long long _d[1000010];
  void init(int __n) {
    _n = __n;
    memset(_d, 0, sizeof(long long) * (_n + 1));
  }
  void ins(int x, long long v) {
    for (; x <= _n; x += x & -x) _d[x] += v;
  }
  long long qq(int x) {
    long long res = 0;
    for (; x; x -= x & -x) res += _d[x];
    return res;
  }
  long long qq_range(int x, int y) {
    long long ret = qq(y);
    if (x) ret -= qq(x - 1);
    return ret;
  }
} bit;
bool invalid(int n, int m) {
  bit.init(m);
  for (int i = (1); i <= (n); ++i) {
    for (auto pp : AA[i]) {
      if (bit.qq_range(pp.first, pp.second)) return 1;
    }
    bit.ins(AA[i][0].first, 1);
    for (auto pp : AA[i]) {
      bit.ins(pp.second, 1);
    }
  }
  return 0;
}
int l[SIZE], r[SIZE];
int main() {
  MOD = 998244353;
  int n, m;
  R(n, m);
  for (int i = (1); i <= (m); ++i) {
    R(input[i]);
    cnt[input[i]]++;
  }
  for (int i = (1); i <= (m); ++i) {
    if (cnt[input[i]] == 1)
      AA[input[i]].push_back({i, i});
    else {
      if (lt[input[i]]) AA[input[i]].push_back({lt[input[i]], i});
      lt[input[i]] = i;
    }
  }
  if (invalid(n, m)) {
    W(0);
    return 0;
  }
  for (int i = (1); i <= (m - 1); ++i) {
    int x = input[i];
    int y = input[i + 1];
    if (AA[x].back().second < AA[y][0].first) {
      r[x] = y;
      l[y] = x;
    }
  }
  long long res = 1;
  for (int i = (1); i <= (n); ++i) {
    if (!l[i]) {
      int now = i;
      vector<int> cc{now};
      while (r[now]) {
        now = r[now];
        cc.push_back(now);
      }
      res = res * solve(cc) % MOD;
    }
  }
  W(res);
  return 0;
}