Problem: This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of m and the time limit. You need to solve both subtasks in order to hack this 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) — 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.

Note that since in this subtask n = m, this means that c is a permutation of integers 1 through n.

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


7 7
4 5 1 6 2 3 7


Output


165

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>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct mint {
  static unsigned R, RR, Rinv, W, md, mdninv;
  unsigned val;
  mint() {}
  mint(int a) { val = mulR(a); }
  mint(unsigned a) { val = mulR(a); }
  mint(long long a) { val = mulR(a); }
  mint(unsigned long long a) { val = mulR(a); }
  int get_inv(long long a, int md) {
    long long e, s = md, t = a, u = 1, v = 0;
    while (s) {
      e = t / s;
      t -= e * s;
      u -= e * v;
      swap(t, s);
      swap(u, v);
    }
    if (u < 0) {
      u += md;
    }
    return u;
  }
  void setmod(unsigned m) {
    int i;
    unsigned t;
    W = 32;
    md = m;
    R = (1ULL << W) % md;
    RR = (unsigned long long)R * R % md;
    switch (m) {
      case 104857601:
        Rinv = 2560000;
        mdninv = 104857599;
        break;
      case 998244353:
        Rinv = 232013824;
        mdninv = 998244351;
        break;
      case 1000000007:
        Rinv = 518424770;
        mdninv = 2226617417U;
        break;
      case 1000000009:
        Rinv = 171601999;
        mdninv = 737024967;
        break;
      case 1004535809:
        Rinv = 234947584;
        mdninv = 1004535807;
        break;
      case 1007681537:
        Rinv = 236421376;
        mdninv = 1007681535;
        break;
      case 1012924417:
        Rinv = 238887936;
        mdninv = 1012924415;
        break;
      case 1045430273:
        Rinv = 254466304;
        mdninv = 1045430271;
        break;
      case 1051721729:
        Rinv = 257538304;
        mdninv = 1051721727;
        break;
      default:
        Rinv = get_inv(R, md);
        mdninv = 0;
        t = 0;
        for (i = 0; i < (int)W; i++) {
          if (t % 2 == 0) {
            t += md;
            mdninv |= (1U << i);
          }
          t /= 2;
        }
    }
  }
  unsigned mulR(unsigned a) { return (unsigned long long)a * R % md; }
  unsigned mulR(int a) {
    if (a < 0) {
      a = a % md + md;
    }
    return mulR((unsigned)a);
  }
  unsigned mulR(unsigned long long a) { return mulR((unsigned)(a % md)); }
  unsigned mulR(long long a) {
    a %= md;
    if (a < 0) {
      a += md;
    }
    return mulR((unsigned)a);
  }
  unsigned reduce(unsigned T) {
    unsigned m = T * mdninv,
             t = (unsigned)((T + (unsigned long long)m * md) >> W);
    if (t >= md) {
      t -= md;
    }
    return t;
  }
  unsigned reduce(unsigned long long T) {
    unsigned m = (unsigned)T * mdninv,
             t = (unsigned)((T + (unsigned long long)m * md) >> W);
    if (t >= md) {
      t -= md;
    }
    return t;
  }
  unsigned get() { return reduce(val); }
  mint &operator+=(mint a) {
    val += a.val;
    if (val >= md) {
      val -= md;
    }
    return *this;
  }
  mint &operator-=(mint a) {
    if (val < a.val) {
      val = val + md - a.val;
    } else {
      val -= a.val;
    }
    return *this;
  }
  mint &operator*=(mint a) {
    val = reduce((unsigned long long)val * a.val);
    return *this;
  }
  mint &operator/=(mint a) { return *this *= a.inverse(); }
  mint operator+(mint a) { return mint(*this) += a; }
  mint operator-(mint a) { return mint(*this) -= a; }
  mint operator*(mint a) { return mint(*this) *= a; }
  mint operator/(mint a) { return mint(*this) /= a; }
  mint operator+(int a) { return mint(*this) += mint(a); }
  mint operator-(int a) { return mint(*this) -= mint(a); }
  mint operator*(int a) { return mint(*this) *= mint(a); }
  mint operator/(int a) { return mint(*this) /= mint(a); }
  mint operator+(long long a) { return mint(*this) += mint(a); }
  mint operator-(long long a) { return mint(*this) -= mint(a); }
  mint operator*(long long a) { return mint(*this) *= mint(a); }
  mint operator/(long long a) { return mint(*this) /= mint(a); }
  mint operator-(void) {
    mint res;
    if (val) {
      res.val = md - val;
    } else {
      res.val = 0;
    }
    return res;
  }
  operator bool(void) { return val != 0; }
  operator int(void) { return get(); }
  operator long long(void) { return get(); }
  mint inverse() {
    int a = val, b = md, t, u = 1, v = 0;
    mint res;
    while (b) {
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if (u < 0) {
      u += md;
    }
    res.val = (unsigned long long)u * RR % md;
    return res;
  }
  mint pw(unsigned long long b) {
    mint a(*this), res;
    res.val = R;
    while (b) {
      if (b & 1) {
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  bool operator==(int a) { return mulR(a) == val; }
  bool operator!=(int a) { return mulR(a) != val; }
};
mint operator+(int a, mint b) { return mint(a) += b; }
mint operator-(int a, mint b) { return mint(a) -= b; }
mint operator*(int a, mint b) { return mint(a) *= b; }
mint operator/(int a, mint b) { return mint(a) /= b; }
mint operator+(long long a, mint b) { return mint(a) += b; }
mint operator-(long long a, mint b) { return mint(a) -= b; }
mint operator*(long long a, mint b) { return mint(a) *= b; }
mint operator/(long long a, mint b) { return mint(a) /= b; }
inline void rd(int &x) {
  int k, m = 0;
  x = 0;
  for (;;) {
    k = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      x = k - '0';
      break;
    }
  }
  for (;;) {
    k = getchar();
    if (k < '0' || k > '9') {
      break;
    }
    x = x * 10 + k - '0';
  }
  if (m) {
    x = -x;
  }
}
inline void wt_L(char a) { putchar(a); }
inline void wt_L(int x) {
  char f[10];
  int m = 0, s = 0;
  if (x < 0) {
    m = 1;
    x = -x;
  }
  while (x) {
    f[s++] = x % 10;
    x /= 10;
  }
  if (!s) {
    f[s++] = 0;
  }
  if (m) {
    putchar('-');
  }
  while (s--) {
    putchar(f[s] + '0');
  }
}
inline void wt_L(mint x) {
  int i;
  i = (int)x;
  wt_L(i);
}
template <class S, class T>
inline S chmin(S &a, T b) {
  if (a > b) {
    a = b;
  }
  return a;
}
template <class S, class T>
inline S chmax(S &a, T b) {
  if (a < b) {
    a = b;
  }
  return a;
}
unsigned mint::R, mint::RR, mint::Rinv, mint::W, mint::md, mint::mdninv;
int N;
int M;
int C[1000000];
int vis[1000][1000];
mint dp[1000][1000];
int gmn[500];
int gmx[500];
mint solve(int a, int b) {
  int dame, i, j, k, mn, mx;
  mint lef, mul, rig;
  if (a > b) {
    return 1;
  }
  if (vis[a][b]) {
    return dp[a][b];
  }
  vis[a][b] = 1;
  j = 1073709056;
  for (i = a; i < b + 1; i++) {
    chmin(j, C[i]);
  }
  mn = M;
  mx = -1;
  for (i = a; i < b + 1; i++) {
    if (j == C[i]) {
      chmin(mn, i);
      chmax(mx, i);
    }
  }
  lef = rig = 0;
  dame = mn;
  for (i = mn; i >= a; i--) {
    chmin(dame, gmn[C[i]]);
    if (i <= dame) {
      lef += solve(a, i - 1) * solve(i, mn - 1);
    }
  }
  dame = mx;
  for (i = mx; i <= b; i++) {
    chmax(dame, gmx[C[i]]);
    if (i >= dame) {
      rig += solve(mx + 1, i) * solve(i + 1, b);
    }
  }
  mul = 1;
  for (i = mn; i < mx + 1; i++) {
    if (C[i] == j) {
      continue;
    }
    k = i;
    while (C[k + 1] != j) {
      k++;
    }
    mul *= solve(i, k);
    i = k;
  }
  return dp[a][b] = lef * rig * mul;
}
int main() {
  int i, j, k, mn, mx;
  mint res;
  {
    mint x;
    x.setmod(998244353);
  }
  rd(N);
  rd(M);
  {
    int Lj4PdHRW;
    for (Lj4PdHRW = 0; Lj4PdHRW < M; Lj4PdHRW++) {
      rd(C[Lj4PdHRW]);
      C[Lj4PdHRW] += (-1);
    }
  }
  k = 1;
  for (i = 1; i < M; i++) {
    if (C[i] == C[i - 1]) {
      continue;
    }
    C[k++] = C[i];
  }
  M = k;
  if (M > 2 * N) {
    wt_L(0);
    wt_L('\n');
    return 0;
  }
  for (k = 0; k < N; k++) {
    mn = M + 1;
    mx = -1;
    for (i = 0; i < M; i++) {
      if (C[i] == k) {
        chmin(mn, i);
        chmax(mx, i);
      }
    }
    gmn[k] = mn;
    gmx[k] = mx;
    for (i = mn; i < mx + 1; i++) {
      if (C[i] < k) {
        wt_L(0);
        wt_L('\n');
        return 0;
      }
    }
  }
  res = solve(0, M - 1);
  wt_L(res);
  wt_L('\n');
  return 0;
}