#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
inline long long qpow(long long a, long long b = 998244353 - 2) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % 998244353)
    if (b & 1) res = res * a % 998244353;
  return res;
}
inline void add(long long& a, long long b) {
  a += b;
  if (a > 998244353) a %= 998244353;
}
long long n, m;
long long f[1005][1005], a[1005], mn[1005][1005];
vector<long long> p[1005];
long long dfs(long long l, long long r) {
  if (l > r) return 1;
  if (~f[l][r]) return f[l][r];
  long long c = mn[l][r], L = p[c].front(), R = p[c].back();
  long long& res = f[l][r];
  if (L < l || R > r) return res = 0;
  long long resl = 0, resr = 0;
  for (register long long k = (l); k <= (L); ++k)
    add(resl, dfs(l, k - 1) * dfs(k, L - 1) % 998244353);
  for (register long long k = (R); k <= (r); ++k)
    add(resr, dfs(R + 1, k) * dfs(k + 1, r) % 998244353);
  res = resl * resr % 998244353;
  for (long long k = 1; k < p[c].size(); ++k)
    res = res * dfs(p[c][k - 1] + 1, p[c][k] - 1) % 998244353;
  return res;
}
signed main() {
  n = read(), m = read();
  for (register long long i = (1); i <= (m); ++i) a[i] = read();
  m = unique(a + 1, a + m + 1) - a - 1;
  if (m > 2 * n) {
    puts("0");
    return 0;
  }
  for (register long long i = (1); i <= (m); ++i)
    p[a[i]].push_back(i), mn[i][i] = a[i];
  for (register long long l = (2); l <= (m); ++l)
    for (long long i = 1, j = i + l - 1; j <= m; ++i, ++j)
      mn[i][j] = min(mn[i][j - 1], mn[i + 1][j]);
  memset(f, -1, sizeof f);
  cout << dfs(1, m);
  return 0;
}
