This is the second subtask of problem F. The only differences between this and the first subtask are the constraints on the value of m and the time limit. It is sufficient to solve this subtask in order to hack it, but you need to solve both subtasks in order to hack the first one.

There are n+1 distinct colours in the universe, numbered 0 through n. There is a strip of paper m centimetres long initially painted with colour 0. 

Alice took a brush and painted the strip using the following process. For each i from 1 to n, in this order, she picks two integers 0 ≤ a_i < b_i ≤ m, such that the segment [a_i, b_i] is currently painted with a single colour, and repaints it with colour i. 

Alice chose the segments in such a way that each centimetre is now painted in some colour other than 0. Formally, the segment [i-1, i] is painted with colour c_i (c_i ≠ 0). Every colour other than 0 is visible on the strip.

Count the number of different pairs of sequences \\{a_i\}_{i=1}^n, \\{b_i\}_{i=1}^n that result in this configuration. 

Since this number may be large, output it modulo 998244353.

Input

The first line contains a two integers n, m (1 ≤ n ≤ 500, n ≤ m ≤ 10^6) — the number of colours excluding the colour 0 and the length of the paper, respectively.

The second line contains m space separated integers c_1, c_2, …, c_m (1 ≤ c_i ≤ n) — the colour visible on the segment [i-1, i] after the process ends. It is guaranteed that for all j between 1 and n there is an index k such that c_k = j.

Output

Output a single integer — the number of ways Alice can perform the painting, modulo 998244353.

Examples

Input


3 3
1 2 3


Output


5


Input


2 3
1 2 1


Output


1


Input


2 3
2 1 2


Output


0


Input


7 7
4 5 1 6 2 3 7


Output


165


Input


8 17
1 3 2 2 7 8 2 5 5 4 4 4 1 1 6 1 1


Output


20

Note

In the first example, there are 5 ways, all depicted in the figure below. Here, 0 is white, 1 is red, 2 is green and 3 is blue.

<image>

Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour 2.

<image>

In the second example, Alice must first paint segment 0 3 with colour 1 and then segment 1 2 with colour 2. 
#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;
}
