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;
const long long mod = 1e9 + 7;
const int infi = 2147483600;
const long long infl = 1e17;
const long long MOD = 998244353;
int n, m;
struct SegmentTree {
 private:
  int N;
  vector<long long> node;
  long long e;

 public:
  SegmentTree() {}
  SegmentTree(long long e) : e(e) {}
  void __init__(int sz) {
    N = 1;
    while (N < sz) N *= 2;
    node.resize(2 * N - 1, e);
  }
  void build(vector<long long> &v) {
    int sz = int(v.size());
    __init__(sz);
    for (long long i = 0; i < (long long)sz; i++) {
      node[i + N - 1] = v[i];
    }
    for (int i = N - 2; i >= 0; i--) {
      node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
    }
  }
  void update(int k, long long x) {
    k += N - 1;
    node[k] = x;
    while (k > 0) {
      k = (k - 1) / 2;
      node[k] = min(node[2 * k + 1], node[2 * k + 2]);
    }
  }
  void renew(int b, int e, long long x) {
    renew(b, e, 0, 0, N, x);
    return;
  }
  void renew(int b, int e, int k, int l, int r, long long x) {
    if (e <= 0 || b >= N) return;
    if (k > 0) {
      node[k] = min(node[k], node[(k - 1) / 2]);
    }
    if (r < b || e < l) return;
    if (b <= l && r <= e) {
      node[k] = min(node[k], x);
      return;
    } else if (k < N - 1) {
      renew(b, e, 2 * k + 1, l, (l + r) / 2, x);
      renew(b, e, 2 * k + 2, (l + r) / 2, r, x);
      return;
    }
    return;
  }
  long long get(int i) {
    int k = i + N - 1;
    long long res = node[k];
    while (k > 0) {
      k = (k - 1) / 2;
      res = min(res, node[k]);
    }
    return res;
  }
  long long query(int a, int b) { return query(a, b, 0, 0, N); }
  long long query(int a, int b, int k, int l, int r) {
    if (b <= l || r <= a) return e;
    if (a <= l && r <= b) return node[k];
    long long vl, vr;
    vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
    vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
    return min(vl, vr);
  }
  void recalc() {
    for (long long k = 0; k < (long long)N - 1; k++) {
      node[2 * k + 1] = min(node[2 * k * 1], node[k]);
      node[2 * k + 2] = min(node[2 * k * 2], node[k]);
    }
  }
  long long show_one(int i) { return node[i + N - 1]; }
  void show() {
    for (long long i = 0; i < (long long)N; i++) cout << node[i] << " ";
    cout << endl;
    return;
  }
};
SegmentTree seg(infl);
long long dp[505][505];
long long idx[505];
long long calc(int l, int r) {
  if (dp[l][r] != -1) {
    return dp[l][r];
  }
  if (l + 1 == r) {
    dp[l][r] = 1;
    return 1;
  }
  if (l == r) {
    dp[l][r] = 1;
    return 1;
  }
  int c = seg.query(l, r);
  int cidx = idx[c];
  long long asum = 0, bsum = 0;
  for (long long a = (long long)l; a < (long long)cidx + 1; a++) {
    asum = (asum + calc(l, a) * calc(a, cidx) % MOD) % MOD;
  }
  for (long long b = (long long)cidx + 1; b < (long long)r + 1; b++) {
    bsum = (bsum + calc(cidx + 1, b) * calc(b, r) % MOD) % MOD;
  }
  dp[l][r] = (asum * bsum) % MOD;
  return dp[l][r];
}
int main() {
  cin >> n >> m;
  vector<long long> color(n);
  for (long long i = 0; i < (long long)n; i++) {
    cin >> color[i];
    idx[color[i]] = i;
  }
  for (long long i = 0; i < (long long)n + 1; i++)
    for (long long j = 0; j < (long long)n + 1; j++) dp[i][j] = -1;
  seg.build(color);
  cout << calc(0, n) << endl;
}