#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
vector<int> logn(1025);
int main() {
  logn[1] = 0;
  for (int i = 2; i < 1025; ++i) {
    logn[i] = logn[i / 2] + 1;
  }
  long long n, m;
  cin >> n >> m;
  vector<int> str;
  int loc = 0, cnt = 0;
  cin >> loc;
  vector<int> nc(n + 1, 0);
  for (int i = 0; i < m - 1; ++i) {
    int x;
    cin >> x;
    if (x != loc) {
      str.push_back(loc);
      nc[loc]++;
      loc = x;
    }
  }
  str.push_back(loc);
  nc[loc]++;
  m = str.size();
  if (m > 1024) {
    cout << 0;
    return 0;
  }
  vector<vector<pair<int, set<int>>>> go(logn[m] + 1,
                                         vector<pair<int, set<int>>>(m));
  for (int i = 0; i < m; ++i) {
    go[0][i] = {str[i], {i}};
  }
  for (int lg = 1; lg <= logn[m]; ++lg) {
    for (int i = 0; i < m; ++i) {
      if (i + (1 << (lg - 1)) < m) {
        if (go[lg - 1][i].first == go[lg - 1][i + (1 << (lg - 1))].first) {
          auto p = go[lg - 1][i + (1 << (lg - 1))].second;
          go[lg][i] = go[lg - 1][i];
          go[lg][i].second.insert(p.begin(), p.end());
        } else {
          go[lg][i] = min(go[lg - 1][i], go[lg - 1][i + (1 << (lg - 1))]);
        }
      } else {
        go[lg][i] = go[lg - 1][i];
      }
    }
  }
  vector<vector<long long>> dp(m + 1, vector<long long>(m + 1, 1));
  for (int len = 1; len <= m; ++len) {
    int lg = logn[len];
    for (int i = 0; i <= m - len; ++i) {
      pair<int, set<int>> p;
      if (go[lg][i].first == go[lg][i + len - (1 << lg)].first) {
        auto q = go[lg][i + len - (1 << lg)].second;
        p = go[lg][i];
        p.second.insert(q.begin(), q.end());
      } else {
        p = min(go[lg][i], go[lg][i + len - (1 << lg)]);
      }
      int nloc = p.second.size();
      if (nloc < nc[p.first]) {
        dp[i][i + len] = 0;
        continue;
      }
      auto it = p.second.begin();
      for (int j = 0; j < nloc - 1; ++j) {
        auto nit = it;
        nit++;
        dp[i][i + len] *= dp[(*it) + 1][(*nit)];
        dp[i][i + len] %= MOD;
        it++;
      }
      int li = (*(p.second.begin())), ri = (*(p.second.rbegin()));
      long long left = 0, right = 0;
      for (int j = i; j <= li; ++j) {
        left += dp[j][li] * dp[i][j];
        left %= MOD;
      }
      for (int j = ri + 1; j <= i + len; ++j) {
        right += dp[ri + 1][j] * dp[j][i + len];
        right %= MOD;
      }
      dp[i][i + len] *= ((left * right) % MOD);
      dp[i][i + len] %= MOD;
    }
  }
  cout << dp[0][m] << endl;
  return 0;
}
