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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class T = int>
inline T readInt();
inline double readDouble();
inline int readUInt();
inline int readChar();
inline void readWord(char *s);
inline bool readLine(char *s);
inline bool isEof();
inline int getChar();
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();
inline std::string readString();
template <class T>
inline void writeInt(T x, char end = 0, int len = -1);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void writeDouble(double x, int len = 0);
inline void flush();
static struct buffer_flusher_t {
  ~buffer_flusher_t() { flush(); }
} buffer_flusher;
using namespace std;
inline void init() {
  srand(time(0));
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
template <class T, class S>
inline void rmax(T &a, S b) {
  a = max(a, (T)b);
}
template <class T, class S>
inline void rmin(T &a, S b) {
  a = min(a, (S)b);
}
inline long long mul(long long a, long long b, long long m) {
  return a * b % m;
}
inline long long binpow(long long n, long long p, long long m) {
  if (!p) return 1;
  if (p & 1) return mul(n, binpow(n, p - 1, m), m);
  long long v = binpow(n, p / 2, m);
  return mul(v, v, m);
}
inline bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) return 0;
  return 1;
}
inline vector<long long> factor(long long n) {
  vector<long long> ans;
  for (long long i = 2; i * i <= n; ++i)
    while (n % i == 0) ans.push_back(i), n /= i;
  if (n != 1) ans.push_back(n);
  return ans;
}
inline vector<long long> divisors(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  return ret;
}
inline vector<pair<long long, int>> factor_pows(long long n) {
  auto fac = factor(n);
  vector<pair<long long, int>> ret;
  int L = 0;
  while (L < (int)fac.size()) {
    int R = L;
    while (R < (int)fac.size() && fac[R] == fac[L]) ++R;
    ret.push_back({fac[L], R - L});
    L = R;
  }
  return ret;
}
inline long long gen_random_prime(long long L = (int)1e9) {
  L += rand() % 4242;
  while (!is_prime(L)) ++L;
  return L;
}
inline long long nmod(long long a, long long m) { return (a % m + m) % m; }
inline int mrand() { return abs((1LL * rand() << 15) + rand()); }
struct HashedString {
  string s;
  vector<long long> MOD, POW;
  vector<vector<long long>> hash;
  vector<vector<long long>> pows;
  string substr(int L, int n) { return s.substr(L, n); }
  int size() const { return s.size(); }
  char operator[](int n) const { return s[n]; }
  vector<long long> get_hash(int L, int R) {
    vector<long long> ret;
    for (int i = 0; i < (int)hash.size(); ++i) {
      ret.push_back(nmod(hash[i][R] - hash[i][L] * pows[i][R - L], MOD[i]));
    }
    return ret;
  }
  bool equal(int L1, int R1, int L2, int R2) {
    return get_hash(L1, R1) == get_hash(L2, R2);
  }
  void operator+=(char c) {
    s += c;
    for (int i = 0; i < (int)hash.size(); ++i) {
      long long m = MOD[i], p = POW[i], cp = pows[i].back(),
                cm = hash[i].back();
      cm = (cm * p + c) % m, cp = cp * p % m;
      hash[i].push_back(cm);
      pows[i].push_back(cp);
    }
  }
  void operator+=(const string &oth) {
    for (int i = 0; i < (int)hash.size(); ++i)
      for (char c : oth) (*this) += c;
  }
  HashedString(const string &s, int n = 1) {
    for (int i = 0; i < n; ++i) {
      MOD.push_back(gen_random_prime());
      POW.push_back(gen_random_prime());
      hash.push_back({0}), pows.push_back({1});
    }
    (*this) += s;
  }
};
const int MAXN = 542;
const int MOD = 998244353;
int a[MAXN];
bool used[MAXN][MAXN];
int dp[MAXN][MAXN];
int pos_of_min[MAXN][MAXN];
int n, m;
inline int lazy_dp(int L, int R) {
  if (L >= R) {
    return 1;
  }
  if (used[L][R]) {
    return dp[L][R];
  }
  used[L][R] = true;
  int x = pos_of_min[L][R];
  long long sum1 = 0;
  long long sum2 = 0;
  for (int l = L; l <= x; ++l) {
    sum1 += 1LL * lazy_dp(L, l - 1) * lazy_dp(l, x - 1);
    sum1 %= MOD;
  }
  for (int r = x; r <= R; ++r) {
    sum2 += 1LL * lazy_dp(x + 1, r) * lazy_dp(r + 1, R);
    sum2 %= MOD;
  }
  sum1 %= MOD;
  sum2 %= MOD;
  return dp[L][R] = 1LL * sum1 * sum2 % MOD;
}
signed main() {
  init();
  n = readInt();
  m = readInt();
  for (int i = 0; i < n; ++i) {
    a[i] = readInt();
  }
  for (int L = 0; L < n; ++L) {
    for (int R = L + 1; R < n; ++R) {
      int pos = L;
      for (int j = L + 1; j <= R; ++j) {
        if (a[j] < a[pos]) {
          pos = j;
        }
      }
      pos_of_min[L][R] = pos;
    }
  }
  cout << lazy_dp(0, n - 1) << endl;
}
static const int buf_size = 4096;
static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
inline string readString() {
  const int MAX = 1e6 + 42;
  static char buf[MAX];
  readWord(buf);
  return string(buf);
}
inline bool isEof() {
  if (buf_pos == buf_len) {
    buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
    if (buf_pos == buf_len) return 1;
  }
  return 0;
}
inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; }
inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; }
inline bool seekEof() {
  int c;
  while ((c = peekChar()) != -1 && c <= 32) buf_pos++;
  return c == -1;
}
inline void skipBlanks() {
  while (!isEof() && buf[buf_pos] <= 32U) buf_pos++;
}
inline int readChar() {
  int c = getChar();
  while (c != -1 && c <= 32) c = getChar();
  return c;
}
inline int readUInt() {
  int c = readChar(), x = 0;
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return x;
}
template <class T>
inline T readInt() {
  int second = 1, c = readChar();
  T x = 0;
  if (c == '-')
    second = -1, c = getChar();
  else if (c == '+')
    c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return second == 1 ? x : -x;
}
inline double readDouble() {
  int second = 1, c = readChar();
  double x = 0;
  if (c == '-') second = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  if (c == '.') {
    c = getChar();
    double coef = 1;
    while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 1e-1), c = getChar();
  }
  return second == 1 ? x : -x;
}
inline void readWord(char *second) {
  int c = readChar();
  while (c > 32) *second++ = c, c = getChar();
  *second = 0;
}
inline bool readLine(char *second) {
  int c = getChar();
  while (c != '\n' && c != -1) *second++ = c, c = getChar();
  *second = 0;
  return c != -1;
}
static int write_buf_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_buf_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
  write_buf[write_buf_pos++] = x;
}
inline void flush() {
  if (write_buf_pos)
    fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
}
template <class T>
inline void writeInt(T x, char end, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  char second[24];
  int n = 0;
  while (x || !n) second[n++] = '0' + x % 10, x /= 10;
  while (n < output_len) second[n++] = '0';
  while (n--) writeChar(second[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *second) {
  while (*second) writeChar(*second++);
}
inline void writeDouble(double x, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  int t = (int)x;
  writeInt(t), x -= t;
  writeChar('.');
  for (int i = output_len - 1; i > 0; i--) {
    x *= 10;
    t = std::min(9, (int)x);
    writeChar('0' + t), x -= t;
  }
  x *= 10;
  t = std::min(9, (int)(x + 0.5));
  writeChar('0' + t);
}