#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
inline long long sum(long long a, long long b) {
  a += b;
  if (a > MOD) a -= MOD;
  return a;
}
inline long long mult(long long a, long long b) { return (a * b) % MOD; }
const int N = 2020;
long long f[N];
long long dp[N][N];
long long DP[N][N];
long long solve(vector<int>& a) {
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) dp[i][j] = DP[i][j] = 0;
  int n = (int)a.size();
  for (int i = 0; i <= n + 2; ++i) {
    dp[i][i] = DP[i][i] = 1;
    for (int j = 0; j < i; ++j) DP[i][j] = 1;
  }
  for (int len = 1; len < n; ++len) {
    for (int i = 1; i <= n - len; ++i) {
      int posMin = i;
      for (int j = i + 1; j <= i + len; ++j)
        if (a[j - 1] < a[posMin - 1]) posMin = j;
      dp[i][i + len] = mult(DP[i][posMin - 1], DP[posMin + 1][i + len]);
      DP[i][i + len] = dp[i][i + len];
      for (int j = i; j < i + len; ++j)
        DP[i][i + len] =
            sum(DP[i][i + len], mult(dp[i][j], DP[j + 1][i + len]));
    }
  }
  return DP[1][n];
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> a;
  for (int i = 0; i < m; ++i) {
    static int x;
    scanf("%d", &x);
    if (a.empty() || a.back() != x) a.push_back(x);
  }
  for (int col = n; col > 0; --col) {
    static int first, last;
    first = last = -1;
    for (int i = 0; i < (int)a.size(); ++i) {
      if (a[i] != col) continue;
      if (first == -1) first = i;
      last = i;
    }
    if (first == -1) continue;
    f[col] = 1;
    if (first == last) continue;
    vector<int> v;
    for (int i = first + 1; i <= last; ++i) {
      if (a[i] < col) {
        printf("0");
        return 0;
      }
      if (a[i] != col) {
        f[col] = mult(f[col], f[a[i]]);
        v.push_back(a[i]);
      } else {
        f[col] = mult(f[col], solve(v));
        v.clear();
      }
    }
    vector<int> b;
    for (int i = 0; i <= first; ++i) b.push_back(a[i]);
    for (int i = last + 1; i < (int)a.size(); ++i) b.push_back(a[i]);
    a.clear();
    for (int x : b) a.push_back(x);
  }
  long long ans = 1;
  for (int col : a) ans = mult(ans, f[col]);
  ans = mult(ans, solve(a));
  printf("%lld", ans);
}
