#include <bits/stdc++.h>
using namespace std;
const int N = 1005, K = 1e6 + 7, M = 998244353;
int a[K];
int n, m;
int l[N], r[N];
long long dp[N][N];
vector<int> pos[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> a[i];
  m = unique(a + 1, a + m + 1) - a - 1;
  for (int i = 1; i <= m; i++) {
    if (!l[a[i]]) l[a[i]] = i;
    r[a[i]] = i;
    pos[a[i]].push_back(i);
  }
  if (m >= 2 * n) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    dp[i][i - 1] = 1;
  }
  dp[m + 1][m] = 1;
  for (int len = 1; len <= m; len++) {
    for (int L = 1; L + len - 1 <= m; L++) {
      int R = L + len - 1;
      int v = K;
      for (int i = L; i <= R; i++)
        if (a[i] < v) {
          v = a[i];
        }
      if (!(L <= l[v] && r[v] <= R)) continue;
      long long left = 0, right = 0;
      for (int rr = r[v]; rr <= R; rr++)
        if (a[rr] < v)
          continue;
        else
          right = (right + dp[r[v] + 1][rr] * dp[rr + 1][R]) % M;
      for (int ll = l[v]; ll >= L; ll--)
        if (a[ll] < v)
          continue;
        else
          left = (left + dp[L][ll - 1] * dp[ll][l[v] - 1]) % M;
      dp[L][R] = (left * right) % M;
      for (int i = 1; i < pos[v].size(); i++)
        dp[L][R] = (dp[L][R] * dp[pos[v][i - 1] + 1][pos[v][i] - 1]) % M;
    }
  }
  cout << dp[1][m] << endl;
}
