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;
int n, m;
vector<pair<int, int>> init_range;
vector<vector<pair<int, int>>> center;
vector<vector<int>> left_v, right_v, color_pos;
unordered_map<long long, int> dp;
vector<int> arr;
struct STNode {
  int left, right, val;
  STNode *left_child, *right_child;
  STNode(int l, int r) {
    left = l, right = r, val = arr[l];
    if (left != right) {
      int mid = (left + right) >> 1;
      left_child = new STNode(left, mid);
      right_child = new STNode(mid + 1, right);
      val = min(left_child->val, right_child->val);
    }
  }
  int query(int l, int r) {
    if (right < l || left > r) {
      return ((long long)1e9 + 10);
    } else if (left >= l && right <= r) {
      return val;
    } else {
      int v1 = left_child->query(l, r);
      int v2 = right_child->query(l, r);
      return min(v1, v2);
    }
  }
};
STNode *st;
int go(int l, int r) {
  long long key = ((l) * ((long long)1e6 + 10) + (r));
  if (l > r) {
    return 1;
  } else if (dp.find(key) != dp.end()) {
    return dp[key];
  } else {
    long long ans = 0;
    int c = st->query(l, r);
    long long center_pieces = 1;
    for (pair<int, int> &it : center[c]) {
      center_pieces *= go(it.first, it.second);
      if (center_pieces > ((long long)1e9 + 10)) center_pieces %= 998244353LL;
    }
    long long left_vals = 0;
    for (int i = left_v[c].size() - 1; i >= 0 && left_v[c][i] >= l; --i) {
      long long val = 1LL * go(l, left_v[c][i] - 1) *
                      go(left_v[c][i], init_range[c].first - 1);
      left_vals += val;
      if (left_vals > ((long long)1e9 + 10) * ((long long)1e9 + 10))
        left_vals %= 998244353LL;
    }
    long long right_vals = 0;
    for (int j = 0; j < right_v[c].size() && right_v[c][j] <= r; ++j) {
      long long val = 1LL * go(init_range[c].second + 1, right_v[c][j]) *
                      go(right_v[c][j] + 1, r);
      right_vals = right_vals + val;
      if (right_vals > ((long long)1e9 + 10) * ((long long)1e9 + 10))
        right_vals %= 998244353LL;
    }
    if (left_vals > ((long long)1e9 + 10)) left_vals %= 998244353LL;
    if (right_vals > ((long long)1e9 + 10)) right_vals %= 998244353LL;
    ans = (left_vals * right_vals);
    if (ans > ((long long)1e9 + 10)) ans %= 998244353LL;
    return dp[key] = (ans * center_pieces) % 998244353LL;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  arr.assign(m, 0);
  init_range.assign(n + 1, {m + 1, -1});
  left_v.assign(n + 1, vector<int>());
  right_v.assign(n + 1, vector<int>());
  center.assign(n + 1, vector<pair<int, int>>());
  color_pos.assign(n + 1, vector<int>());
  for (int i = 0; i < m; ++i) {
    cin >> arr[i];
    color_pos[arr[i]].push_back(i);
    init_range[arr[i]].first = min(init_range[arr[i]].first, i);
    init_range[arr[i]].second = max(init_range[arr[i]].second, i);
  }
  st = new STNode(0, m - 1);
  for (int c = 1; c <= n; ++c) {
    if (st->query(init_range[c].first, init_range[c].second) < c) {
      cout << "0\n";
      return 0;
    }
  }
  for (int c = 1; c <= n; ++c) {
    left_v[c].push_back(init_range[c].first);
    right_v[c].push_back(init_range[c].second);
    for (int d = c + 1; d <= n; ++d) {
      if (init_range[d].first < init_range[c].first) {
        int curr = init_range[d].first;
        for (int d2 = d + 1; d2 <= n; ++d2) {
          if (init_range[d2].second > curr) {
            curr = min(curr, init_range[d2].first);
          }
        }
        if (st->query(curr, init_range[c].second) == c) {
          left_v[c].push_back(curr);
        }
      } else if (init_range[d].second > init_range[c].second) {
        int curr = init_range[d].second;
        for (int d2 = d + 1; d2 <= n; ++d2) {
          if (init_range[d2].first < curr) {
            curr = max(curr, init_range[d2].second);
          }
        }
        if (st->query(init_range[c].first, curr) == c) {
          right_v[c].push_back(curr);
        }
      }
    }
  }
  for (int c = 1; c <= n; ++c) {
    sort(left_v[c].begin(), left_v[c].end());
    sort(right_v[c].begin(), right_v[c].end());
    left_v[c].erase(unique(left_v[c].begin(), left_v[c].end()),
                    left_v[c].end());
    right_v[c].erase(unique(right_v[c].begin(), right_v[c].end()),
                     right_v[c].end());
  }
  for (int c = 1; c <= n; ++c) {
    for (int i = 0; i < color_pos[c].size() - 1; ++i) {
      int p1 = color_pos[c][i];
      int p2 = color_pos[c][i + 1];
      if (p1 + 1 != p2) {
        center[c].push_back({p1 + 1, p2 - 1});
      }
    }
  }
  cout << go(0, m - 1) << "\n";
}