#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
const int MAXM = 1000 * 1000;
const int MOD = 998244353;
long long dp[MAXN][MAXN];
long long need[MAXN][MAXN];
int c[MAXM];
long long solve(vector<int>& c) {
  int n = ((int)(c.size()));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = 0;
      need[i][j] = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    dp[i][i] = 1;
    need[i][i] = 2;
  }
  for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
      int r = l + len - 1;
      int mi = l;
      for (int k = l; k <= r; k++) {
        if (c[k] < c[mi]) {
          mi = k;
        }
      }
      int k = mi;
      dp[l][r] +=
          (l <= k - 1 ? need[l][k - 1] : 1) * (k + 1 <= r ? need[k + 1][r] : 1);
      dp[l][r] %= MOD;
      for (int k = l; k <= r + 1; k++) {
        need[l][r] += (l <= k - 1 ? dp[l][k - 1] : 1) * (k <= r ? dp[k][r] : 1);
        need[l][r] %= MOD;
      }
    }
  }
  return dp[0][n - 1];
}
vector<int> where[MAXN];
long long solve(int l, int r, int time) {
  if (l > r) {
    return 1;
  }
  long long ans = 1;
  vector<int> colors;
  int i = l;
  while (i <= r) {
    int color = c[i];
    colors.push_back(color);
    if (color < time) {
      return 0;
    }
    if (where[color][0] != i) {
      return 0;
    }
    for (int j = 1; j < ((int)(where[color].size())); j++) {
      ans *= solve(where[color][j - 1] + 1, where[color][j] - 1, color);
      ans %= MOD;
    }
    i = where[color].back() + 1;
    if (i > r + 1) {
      return 0;
    }
  }
  assert(i == r + 1);
  ans *= solve(colors);
  ans %= MOD;
  return ans;
}
int main(int argc, const char* argv[]) {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    scanf("%i", c + i);
    where[c[i]].push_back(i);
  }
  cout << solve(0, m - 1, 0) << endl;
  return 0;
}
