#include <bits/stdc++.h>
using namespace std;
int n, m;
int L[1005], R[1005];
int c[1000005];
long long dp[1005][1005];
vector<int> what;
int rev[1000005];
vector<int> f[1005];
long long run(int p, int q) {
  assert(p < 1005 && q < 1005);
  if (p == -1 || q == -1) return 0;
  if (dp[p][q] != -1) return dp[p][q];
  int l = what[p];
  int r = what[q];
  if (r < l) swap(l, r);
  int mn = 1;
  for (int i = 1; i <= n; i++) {
    auto itr = lower_bound(f[i].begin(), f[i].end(), l);
    if (itr != f[i].end() && (*itr) <= r) {
      mn = i;
      break;
    }
  }
  long long x = 0, y = 0;
  if (L[mn] < l || r < R[mn]) return dp[p][q] = 0;
  for (int i = 0; i < what.size(); i++) {
    int t = what[i];
    if (l <= t && t <= L[mn]) {
      if (l < t && t < L[mn])
        x = (x + run(rev[l], rev[t - 1]) * run(rev[t], rev[L[mn] - 1])) %
            998244353;
      else if (l == t && t < L[mn])
        x = (x + run(rev[t], rev[L[mn] - 1])) % 998244353;
      else if (l < t && t == L[mn])
        x = (x + run(rev[l], rev[t - 1])) % 998244353;
      else
        x = (x + 1) % 998244353;
    }
  }
  for (int i = 0; i < what.size(); i++) {
    int t = what[i];
    if (t <= r && R[mn] <= t) {
      if (R[mn] < t && t < r)
        y = (y + run(rev[R[mn] + 1], rev[t]) * run(rev[t + 1], rev[r])) %
            998244353;
      else if (R[mn] == t && t < r)
        y = (y + run(rev[t + 1], rev[r])) % 998244353;
      else if (R[mn] < t && t == r)
        y = (y + run(rev[R[mn] + 1], rev[t])) % 998244353;
      else
        y = (y + 1) % 998244353;
    }
  }
  long long ex = 1;
  for (int i = 1; i < (int)f[mn].size() && ex > 0; i++) {
    if (f[mn][i - 1] + 1 <= f[mn][i] - 1) {
      ex = (ex * run(rev[f[mn][i - 1] + 1], rev[f[mn][i] - 1])) % 998244353;
    }
  }
  x = (x * ex) % 998244353;
  x = (x * y) % 998244353;
  return dp[p][q] = x;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> c[i];
    f[c[i]].push_back(i);
    if (L[c[i]] == 0) L[c[i]] = i;
    L[c[i]] = min(L[c[i]], i);
    R[c[i]] = max(R[c[i]], i);
  }
  set<int> all;
  for (int i = 1; i <= n; i++) {
    all.insert(L[i]);
    all.insert(R[i]);
  }
  memset(rev, -1, sizeof rev);
  for (int u : all) {
    what.push_back(u);
    rev[u] = (int)what.size() - 1;
  }
  memset(dp, -1, sizeof dp);
  cout << run(rev[1], rev[m]);
}
