#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]);
}
