#include <bits/stdc++.h>
template <typename T>
class IntegerIterator {
 public:
  using value_type = T;
  using difference_type = std::ptrdiff_t;
  using pointer = T*;
  using reference = T;
  using iterator_category = std::input_iterator_tag;
  explicit IntegerIterator(T value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) const { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) const { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
  using IteratorType = std::reverse_iterator<IntegerIterator<T>>;

 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IteratorType begin() const {
    return IteratorType(IntegerIterator<T>(begin_));
  }
  IteratorType end() const { return IteratorType(IntegerIterator<T>(end_)); }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
template <typename R>
void sort(R& range) {
  std::sort(range.begin(), range.end());
}
template <typename R, typename Comp>
void sort(R& range, Comp comp) {
  std::sort(range.begin(), range.end(), comp);
}
template <typename R>
void reverse(R& range) {
  std::reverse(range.begin(), range.end());
}
template <typename R, typename T>
auto lower_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto lower_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::lower_bound(range.begin(), range.end(), value, comp);
}
template <typename R, typename T>
auto upper_bound(const R& range, const T& value) -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value);
}
template <typename R, typename T, typename Comp>
auto upper_bound(const R& range, const T& value, Comp comp)
    -> decltype(range.begin()) {
  return std::upper_bound(range.begin(), range.end(), value, comp);
}
template <typename R>
auto min_element(const R& range) -> decltype(range.begin()) {
  return std::min_element(range.begin(), range.end());
}
template <typename R>
auto max_element(const R& range) -> decltype(range.begin()) {
  return std::max_element(range.begin(), range.end());
}
template <typename R>
bool next_permutation(R& range) {
  return std::next_permutation(range.begin(), range.end());
}
template <typename T>
void unique(std::vector<T>& range) {
  range.erase(std::unique(range.begin(), range.end()), range.end());
}
template <typename R>
R sorted(R range) {
  sort(range);
  return range;
}
template <typename R, typename Comp>
R sorted(R range, Comp comp) {
  sort(range, comp);
  return range;
}
template <typename R>
R reversed(R range) {
  reverse(range);
  return range;
}
template <typename T>
std::size_t leastSignificantBit(T number) {
  ;
  for (std::size_t i = 0;; ++i) {
    if ((number >> i) & 1) {
      return i;
    }
  }
}
template <typename T>
bool isPowerOf2(T number) {
  return number != 0 && (number & (number - 1)) == 0;
}
template <typename T, typename Operation>
class SparseTable {
 public:
  explicit SparseTable(std::vector<T> elements,
                       const Operation& operation = Operation(),
                       const T& neutralValue = T())
      : operation(operation), neutralValue(neutralValue) {
    std::size_t n = elements.size();
    logarithms.resize(n + 1);
    for (std::size_t i = 2; i < logarithms.size(); ++i) {
      logarithms[i] = logarithms[i - 1];
      if (isPowerOf2(i)) {
        ++logarithms[i];
      }
    }
    table.push_back(std::move(elements));
    table.resize(logarithms[n] + 1, std::vector<T>(n));
    for (auto i : range(static_cast<std::size_t>(1), table.size())) {
      for (std::size_t j = 0; j + (1 << i) <= n; ++j) {
        table[i][j] =
            this->operation(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  T getResult(std::size_t l, std::size_t r) const {
    ;
    if (l == r) {
      return neutralValue;
    }
    auto log = logarithms[r - l];
    ;
    ;
    return operation(table[log][l], table[log][r - (1 << log)]);
  }

 private:
  std::vector<std::size_t> logarithms;
  std::vector<std::vector<T>> table;
  Operation operation;
  T neutralValue;
};
template <bool b, typename T = void>
using enable_if_t = typename std::enable_if<b, T>::type;
template <bool... Bools>
struct Disjunction : std::false_type {};
template <bool First, bool... Others>
struct Disjunction<First, Others...>
    : std::integral_constant<bool, First || Disjunction<Others...>::value> {};
template <typename T, typename... Types>
using IsOneOf = Disjunction<std::is_same<T, Types>::value...>;
template <typename T>
using IsSaneInteger = std::integral_constant<
    bool,
    std::is_integral<T>::value &&
        !IsOneOf<typename std::remove_cv<T>::type, char, signed char,
                 unsigned char, bool, char16_t, char32_t, wchar_t>::value>;
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity() {
  return IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
class Zn {
 public:
  Zn() : value(0) {}
  template <typename U>
  static Zn valueOf(U value) {
    int x = static_cast<int>(value % mod());
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  template <typename U>
  Zn& operator=(U rhs) {
    return *this = Zn::valueOf(rhs);
  }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod()) {
      value -= mod();
    }
    return *this;
  }
  template <typename U>
  Zn& operator+=(U rhs) {
    return *this += Zn::valueOf(rhs);
  }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod();
    }
    return *this;
  }
  template <typename U>
  Zn& operator-=(U rhs) {
    return *this -= Zn::valueOf(rhs);
  }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    value = static_cast<int>(result % mod());
    return *this;
  }
  template <typename U>
  Zn& operator*=(U rhs) {
    return *this *= Zn::valueOf(rhs);
  }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod() - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  template <typename U>
  Zn& operator/=(U rhs) {
    return *this /= Zn::valueOf(rhs);
  }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod(), x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  template <typename U>
  friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
  template <typename U>
  friend std::istream& operator>>(std::istream&, Zn<U>& zn);
  template <typename U>
  friend bool operator==(const Zn<U>& lhs, const Zn<U>& rhs);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
  constexpr static int mod() { return T::value; }
  template <int N = T::value>
  static constexpr bool correct_or_runtime(int) {
    return N > 0 && N <= (1 << 30);
  }
  static constexpr bool correct_or_runtime(...) { return true; }
  static_assert(
      std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
      "T::value must be int");
  static_assert(correct_or_runtime(0),
                "Mod has to be positive integer up to 1 << 30");
};
template <typename T>
bool operator==(const Zn<T>& lhs, const Zn<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Zn<T>& lhs, U rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Zn<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T, typename U>
Zn<T> operator+(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T, typename U>
Zn<T> operator+(U lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T, typename U>
Zn<T> operator-(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T, typename U>
Zn<T> operator-(U lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T, typename U>
Zn<T> operator*(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T, typename U>
Zn<T> operator*(U lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T, typename U>
Zn<T> operator/(const Zn<T>& lhs, U rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T, typename U>
Zn<T> operator/(U lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
  return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
  int64_t value;
  stream >> value;
  zn.value = static_cast<int>(value % T::value);
  return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
  static Zn<T> identity() { return Zn<T>::valueOf(1); }
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
using Zn7 = ZnConst<1000000007>;
struct Min {
  template <typename T>
  T operator()(const T& l, const T& r) const {
    return std::min(l, r);
  }
};
template <typename T, std::size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(std::size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
using namespace std;
class F2DlinnayaRaznocvetnayaPoloska {
 public:
  static constexpr int kStressCount = 0;
  static void generateTest(std::ostream& test) {}
  void solve(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    vector<int> c(m);
    for (int i : range(m)) {
      in >> c[i];
      --c[i];
    }
    vector<vector<int>> all(n);
    for (int i : range(m)) {
      all[c[i]].push_back(i);
    }
    vector<int> borders;
    for (int i : range(n)) {
      borders.push_back(all[i].front());
      borders.push_back(all[i].back() + 1);
    }
    sort(borders);
    unique(borders);
    vector<int> toId(m + 1, -1);
    for (int i : range(borders.size())) {
      toId[borders[i]] = i;
    }
    int borderCnt = borders.size();
    SparseTable<int, Min> sparse(c, Min(), -5);
    using Z = ZnConst<998244353>;
    auto dp = make_vector<Z>(borderCnt, borderCnt, Z());
    for (int i : range(borderCnt)) {
      dp[i][i] = 1;
    }
    auto get_dp = [&](int l, int r) {
      if (toId[l] == -1) {
        return Z();
      }
      if (toId[r] == -1) {
        return Z();
      }
      return dp[toId[l]][toId[r]];
    };
    vector<int> calcualted(n, false);
    vector<Z> defValue(n);
    auto get_default = [&](int l) {
      if (calcualted[l]) {
        return defValue[l];
      }
      Z defVa = Z::rawValueOf(1);
      for (int x : range<int>(1, all[l].size())) {
        int a = all[l][x - 1];
        int b = all[l][x];
        if (b - a > 1) {
          defVa *= get_dp(a + 1, b);
        }
      }
      defValue[l] = defVa;
      calcualted[l] = true;
      return defVa;
    };
    for (int len : range(1, borderCnt)) {
      for (int lId : range(0, borderCnt - len)) {
        int rId = lId + len;
        int l = borders[lId];
        int r = borders[rId];
        assert(l < r);
        int tVal = sparse.getResult(l, r);
        int tFirst = all[tVal].front();
        int tLast = all[tVal].back();
        if (tFirst < l || tLast >= r) {
          dp[lId][rId] = Z();
          continue;
        }
        Z leftSum{};
        auto firstId = toId[tFirst];
        for (int i : inclusiveRange(lId, firstId)) {
          leftSum += dp[lId][i] * dp[i][firstId];
        }
        Z rightSum{};
        auto lastId = toId[tLast + 1];
        for (int i : inclusiveRange(lastId, rId)) {
          rightSum += dp[lastId][i] * dp[i][rId];
        }
        auto defValue = get_default(tVal);
        dp[lId][rId] = leftSum * rightSum * defValue;
      }
    }
    out << dp[0][borderCnt - 1] << "\n";
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  F2DlinnayaRaznocvetnayaPoloska solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(nullptr);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}
