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;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
void print(ll x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << endl;
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes" << endl;
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No" << endl;
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static random_device rd;
  static mt19937 gen(rd());
  return uniform_int_distribution<ll>(l, r)(gen);
}
using uint = unsigned;
using ull = unsigned long long;
const uint mod = 998244353;
struct mint {
  uint v;
  mint(ll vv = 0) { s(vv % mod + mod); }
  mint& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  mint operator-() const { return mint() - *this; }
  mint& operator+=(const mint& rhs) { return s(v + rhs.v); }
  mint& operator-=(const mint& rhs) { return s(v + mod - rhs.v); }
  mint& operator*=(const mint& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  mint& operator/=(const mint& rhs) { return *this *= rhs.inv(); }
  mint operator+(const mint& rhs) const { return mint(*this) += rhs; }
  mint operator-(const mint& rhs) const { return mint(*this) -= rhs; }
  mint operator*(const mint& rhs) const { return mint(*this) *= rhs; }
  mint operator/(const mint& rhs) const { return mint(*this) /= rhs; }
  mint pow(ll n) const {
    mint res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  mint inv() const { return pow(mod - 2); }
  friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; }
  bool operator<(const mint& r) const { return v < r.v; }
  bool operator==(const mint& r) const { return v == r.v; }
};
const ll vcmax = (1 << 21) + 10;
mint fact[vcmax], finv[vcmax], invs[vcmax];
void initfact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vcmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  finv[vcmax - 1] = fact[vcmax - 1].inv();
  for (ll i = vcmax - 2; i >= 0; i--) {
    finv[i] = finv[i + 1] * (i + 1);
  }
  for (ll i = vcmax - 1; i >= 1; i--) {
    invs[i] = finv[i] * fact[i - 1];
  }
}
mint choose(ll n, ll k) { return fact[n] * finv[n - k] * finv[k]; }
mint binom(ll first, ll second) {
  return fact[first + second] * finv[first] * finv[second];
}
mint catalan(ll n) {
  return binom(n, n) - (n - 1 >= 0 ? binom(n - 1, n + 1) : 0);
}
template <class t, class u>
struct sparsetable {
  vvc<t> first;
  u f;
  sparsetable(const vc<t>& d, u ff) : f(ff) {
    ll n = d.size(), h = topbit(n);
    first.resize(h + 1);
    first[0] = d;
    for (ll j = ll(1); j < ll(h + 1); j++) {
      first[j].resize(n - (1 << j) + 1);
      for (ll i = ll(0); i < ll(n - (1 << j) + 1); i++)
        first[j][i] = f(first[j - 1][i], first[j - 1][i + (1 << (j - 1))]);
    }
  }
  t get(ll second, ll e) {
    assert(second < e);
    ll d = topbit(e - second);
    return f(first[d][second], first[d][e - (1 << d)]);
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  ll n, m;
  cin >> n >> m;
  vi c = readvi(m, -1);
  vvc<ll> pos(n);
  for (ll i = ll(0); i < ll(m); i++) pos[c[i]].push_back(i);
  mint ans = 1;
  vvc<mint> dp(n + 1, vc<mint>(n + 1));
  function<void(ll, ll)> sub = [&](ll l, ll r) {
    if (r <= l) return;
    vi p;
    while (l < r) {
      ll v = c[l];
      assert(pos[v][0] == l);
      for (ll i = ll(1); i < ll(pos[v].size()); i++)
        sub(pos[v][i - 1] + 1, pos[v][i]);
      p.push_back(v);
      l = pos[v].back() + 1;
    }
    ll s = p.size();
    for (ll i = ll(0); i < ll(s + 1); i++) dp[i][i] = 1;
    for (ll i = ll(s) - 1; i >= 0; i--) {
      for (ll j = ll(i + 1); j < ll(s + 1); j++) {
        ll mn = i;
        for (ll k = ll(i); k < ll(j); k++)
          if (p[mn] > p[k]) mn = k;
        mint first, second;
        for (ll k = ll(i); k < ll(mn + 1); k++) first += dp[i][k] * dp[k][mn];
        for (ll k = ll(mn + 1); k < ll(j + 1); k++)
          second += dp[mn + 1][k] * dp[k][j];
        dp[i][j] = first * second;
      }
    }
    ans *= dp[0][s];
  };
  auto imin = [](ll first, ll second) { return min(first, second); };
  sparsetable<ll, decltype(imin)> st(c, imin);
  for (ll i = ll(0); i < ll(n); i++) {
    if (st.get(pos[i].front(), pos[i].back() + 1) < i) {
      print(0);
      return 0;
    }
  }
  sub(0, m);
  cout << ans << endl;
}