#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
int N, M;
int arr[1000013];
vector<int> pos[513];
pair<int, int> sparse[20][1000013];
bitset<513> vis[513];
long long dp[513][513];
int lt[513], rt[513];
int parent[513];
vector<int> edge[513];
long long ans = 1;
vector<int> nums;
pair<int, int> query(int l, int r) {
  int sz = 31 - __builtin_clz(r - l + 1);
  return min(sparse[sz][l], sparse[sz][r - (1 << sz) + 1]);
}
bool cmp(int a, int b) { return lt[a] < lt[b]; }
long long solve(int l, int r) {
  if (l > r) return 1;
  if (vis[l][r]) {
    return dp[l][r];
  }
  vis[l][r] = true;
  int ind = l;
  for (auto i = (l); i < (r + 1); i++) {
    if (nums[i] < nums[ind]) {
      ind = i;
    }
  }
  long long lsum = 0, rsum = 0;
  for (auto i = (l); i < (ind + 1); i++) {
    lsum += solve(l, i - 1) * solve(i, ind - 1);
    lsum %= 998244353;
  }
  for (auto j = (ind); j < (r + 1); j++) {
    rsum += solve(ind + 1, j) * solve(j + 1, r);
    rsum %= 998244353;
  }
  dp[l][r] = lsum * rsum % 998244353;
  return dp[l][r];
}
long long work(vector<int> nums) {
  for (auto i = (0); i < (((int)((nums).size()))); i++) {
    for (auto j = (0); j < (((int)((nums).size()))); j++) {
      vis[i][j] = false;
    }
  }
  return solve(0, ((int)((nums).size())) - 1);
}
void dfs(int u) {
  sort((edge[u]).begin(), (edge[u]).end(), cmp);
  for (int v : edge[u]) {
    dfs(v);
  }
  int rg = lt[u];
  for (int v : edge[u]) {
    if (lt[v] != rg + 1) {
      ans *= work(nums);
      ans %= 998244353;
      nums.clear();
    }
    nums.push_back(v);
    rg = rt[v];
  }
  ans *= work(nums);
  ans %= 998244353;
  nums.clear();
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> M >> N;
  M++;
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
    pos[arr[i]].push_back(i);
  }
  for (auto i = (0); i < (N); i++) {
    sparse[0][i] = {arr[i], i};
  }
  for (auto i = (0); i < (19); i++) {
    for (auto j = (0); j < (N); j++) {
      if (j + (2 << i) > N) break;
      sparse[i + 1][j] = min(sparse[i][j], sparse[i][j + (1 << i)]);
    }
  }
  for (auto i = (1); i < (M); i++) {
    for (auto j = (1); j < (((int)((pos[i]).size()))); j++) {
      int l = pos[i][j - 1], r = pos[i][j];
      if (query(l, r).first != i) {
        cout << "0\n";
        return 0;
      }
    }
    lt[i] = pos[i][0];
    rt[i] = pos[i].back();
  }
  for (auto i = (1); i < (M); i++) {
    parent[i] = 0;
    for (auto j = (1); j < (i); j++) {
      if (lt[j] < lt[i] && rt[i] < rt[j]) {
        parent[i] = j;
      }
    }
    edge[parent[i]].push_back(i);
  }
  dfs(0);
  cout << ans << '\n';
  return 0;
}
