#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 100, LOG = 22, N = 505;
int A[M], n, m;
vector<int> pos[N];
int rmq[M][LOG];
int lg[M];
void preprocess() {
  for (int i = 0; i < m; i++) rmq[i][0] = A[i];
  for (int j = 1; j < LOG; j++) {
    for (int i = 0; i < m; i++) {
      if (i + (1 << j) - 1 < m) {
        rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
      } else
        break;
    }
  }
  for (int i = 2; i < M; i++) {
    lg[i] = lg[i / 2] + 1;
  }
}
int query(int i, int j) {
  int k = lg[j - i + 1];
  int ans = min(rmq[i][k], rmq[j - (1 << k) + 1][k]);
  return ans;
}
const int mod = 998244353;
vector<int> p;
bool vis[N][N];
int dp[N][N];
int solve(int l, int r) {
  if (l > r) return 1;
  if (vis[l][r]) return dp[l][r];
  vis[l][r] = true;
  int MinIdx = -1, Min = 1e9;
  for (int i = l; i <= r; i++) {
    if (Min > p[i]) {
      Min = p[i];
      MinIdx = i;
    }
  }
  int ways1 = 0, ways2 = 0;
  for (int i = l; i <= MinIdx; i++) {
    int cur_ways = 1ll * solve(l, i - 1) * solve(i, MinIdx - 1) % mod;
    ways1 += cur_ways;
    ways1 %= mod;
  }
  for (int i = MinIdx; i <= r; i++) {
    int cur_ways = 1ll * solve(MinIdx + 1, i) * solve(i + 1, r) % mod;
    ways2 += cur_ways;
    ways2 %= mod;
  }
  return dp[l][r] = 1ll * ways1 * ways2 % mod;
}
int dnq(int l, int r) {
  if (l > r) return 1;
  p.clear();
  int ptr = l;
  while (ptr <= r) {
    int x = A[ptr];
    assert(ptr == pos[x][0]);
    assert(pos[x].back() <= r);
    ptr = pos[x].back() + 1;
    p.push_back(x);
  }
  for (int i = 0; i < p.size(); i++) {
    for (int j = 0; j < p.size(); j++) {
      vis[i][j] = dp[i][j] = 0;
    }
  }
  int ways = solve(0, (int)p.size() - 1);
  vector<int> tt = p;
  for (int i = 0; i < tt.size(); i++) {
    int c = tt[i];
    for (int j = 1; j < pos[c].size(); j++) {
      ways = 1ll * ways * dnq(pos[c][j - 1] + 1, pos[c][j] - 1) % mod;
    }
  }
  return ways;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> A[i];
    A[i]--;
    pos[A[i]].push_back(i);
  }
  preprocess();
  for (int i = 0; i < n; i++) {
    int l = pos[i][0], r = pos[i].back();
    if (query(l, r) != i) {
      cout << "0" << endl;
      exit(0);
    }
  }
  cout << dnq(0, m - 1) << endl;
  return 0;
}
