#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
inline long long read1() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
using namespace std;
const int NN = 510;
const int MM = 1000010;
const long long mod = 998244353;
int n, m, a[MM];
int Min[NN], Max[NN];
long long ans = 1;
long long dp[NN][NN], mn[NN][NN];
int Nxt[MM];
long long g(int i, int j) {
  if (i > j) return 1;
  return dp[i][j];
}
void dfs(int l, int r) {
  if (l > r) return;
  vector<int> Mp;
  for (int p = l; p <= r; p = Max[a[p]] + 1) Mp.push_back(a[p]);
  int N = (Mp).size();
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) dp[i][j] = 0;
    dp[i][i] = 1;
    if (i) dp[i][i - 1] = 1;
  }
  for (int i = 0; i < (N); i++) {
    mn[i][i] = i;
    for (int j = i + 1; j <= N - 1; j++) {
      if (Mp[j] < Mp[mn[i][j - 1]])
        mn[i][j] = j;
      else
        mn[i][j] = mn[i][j - 1];
    }
  }
  for (int i = 2; i <= N; i++)
    for (int j = 0; j < (N); j++) {
      int k = j + i - 1;
      if (k >= N) continue;
      long long num1 = 0, num2 = 0;
      int p = mn[j][k];
      for (int l = j; l <= p; l++) (num1 += g(j, l - 1) * g(l, p - 1)) %= mod;
      for (int r = p; r <= k; r++) (num2 += g(p + 1, r) * g(r + 1, k)) %= mod;
      dp[j][k] = num1 * num2 % mod;
    }
  ans *= dp[0][N - 1];
  ans %= mod;
  for (int p = l; p <= r; p = Max[a[p]] + 1) {
    int now = p;
    while (now != Max[a[p]]) {
      int nx = Nxt[now];
      dfs(now + 1, nx - 1);
      now = nx;
    }
  }
}
int nxt[NN];
int main() {
  n = read();
  m = read();
  for (int i = 0; i < (NN); i++) Min[i] = 0x3f3f3f3f, Max[i] = -0x3f3f3f3f;
  for (int i = 1; i <= m; i++) {
    a[i] = read();
    Min[a[i]] = min(Min[a[i]], i);
    Max[a[i]] = max(Max[a[i]], i);
  }
  for (int i = 1; i <= n; i++) nxt[i] = m + 1;
  for (int i = m; i >= 1; i--) Nxt[i] = nxt[a[i]], nxt[a[i]] = i;
  for (int i = 1; i <= n; i++)
    for (int j = Min[i]; j <= Max[i]; j++)
      if (a[j] < i) {
        printf("0\n");
        return 0;
      }
  dfs(1, m);
  printf("%I64d\n", ans);
  return 0;
}
