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;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
template <class T>
inline bool setmin(T& a, T b) {
  if (a > b) return a = b, 1;
  return 0;
}
template <class T>
inline bool setmax(T& a, T b) {
  if (a < b) return a = b, 1;
  return 0;
}
namespace fastio {
template <class T>
istream& operator>>(istream& os, vector<T>& vec) {
  for (auto& u : vec) os >> u;
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  for (auto& u : vec) os << u << " ";
  return os;
}
template <class T1, class T2>
inline istream& operator>>(istream& os, pair<T1, T2>& p) {
  return os >> p.first >> p.second;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << " " << p.second;
}
template <class T>
ostream& operator<<(ostream& os, set<T>& con) {
  for (auto& u : con) os << u << " ";
  return os;
}
void re() {}
template <typename T, typename... args>
void re(T& x, args&... tail) {
  cin >> x;
  re(tail...);
}
void pr() {}
template <typename T>
void pr(const T& x) {
  cout << x;
}
template <typename T, typename... args>
void pr(const T& x, const args&... tail) {
  cout << x << " ";
  pr(tail...);
}
template <typename... args>
void prln(const args&... tail) {
  pr(tail...);
  cout << "\n";
}
}  // namespace fastio
using namespace fastio;
namespace debug {
template <typename _T>
inline void _debug(const char* s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _debug(const char* s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _debug(s + 1, a...);
}
}  // namespace debug
using namespace debug;
constexpr int MOD = 998244353;
constexpr int INF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
const int N = 1007;
ll dp[N][N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, m;
  re(n, m);
  vi a;
  for (int i = (0); (1) > 0 ? i < (m) : i >= (m); i += (1)) {
    int x;
    re(x);
    if (!(int)(a).size() or a.back() != x) {
      a.push_back(x);
    }
  }
  m = (int)(a).size();
  if (m > 2 * n) {
    prln(0);
    return 0;
  }
  vi lewo(n + 1, INF), prawo(n + 1, -1);
  vector<vi> wyst(n + 1);
  for (int i = (0); (1) > 0 ? i < (m) : i >= (m); i += (1)) {
    setmax(prawo[a[i]], i);
    setmin(lewo[a[i]], i);
    wyst[a[i]].push_back(i);
  }
  for (int r = (0); (1) > 0 ? r < (m) : r >= (m); r += (1)) {
    for (int l = (r); (-1) > 0 ? l < (0) : l >= (0); l += (-1)) {
      int id = l;
      for (int i = (l); (1) > 0 ? i < (r + 1) : i >= (r + 1); i += (1)) {
        if (a[i] < a[id]) {
          id = i;
        }
      }
      auto get = [&](int l, int r) {
        if (l > r) return 1ll;
        return dp[l][r];
      };
      if (lewo[a[id]] < l or prawo[a[id]] > r) {
        dp[l][r] = 0;
        continue;
      }
      1999;
      1999;
      ll lr = 0, pr = 0;
      for (int i = (l);
           (1) > 0 ? i < (lewo[a[id]] + 1) : i >= (lewo[a[id]] + 1); i += (1)) {
        lr = (lr + get(l, i - 1) * get(i, lewo[a[id]] - 1)) % MOD;
      }
      for (int i = (prawo[a[id]]); (1) > 0 ? i < (r + 1) : i >= (r + 1);
           i += (1)) {
        1999;
        pr = (pr + get(prawo[a[id]] + 1, i) * get(i + 1, r)) % MOD;
      }
      dp[l][r] = (lr * pr) % MOD;
      1999;
      for (int i = (0); (1) > 0 ? i < ((int)(wyst[a[id]]).size() - 1)
                                : i >= ((int)(wyst[a[id]]).size() - 1);
           i += (1)) {
        int x = wyst[a[id]][i] + 1, y = wyst[a[id]][i + 1];
        if (x != y) {
          1999;
          1999;
          dp[l][r] *= get(x, y - 1);
          dp[l][r] %= MOD;
        }
      }
    }
  }
  prln(dp[0][m - 1]);
}