CF1178F1.Short Colorful Strip

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 \leq a_i \lt b_i \leq 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 \neq 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$.

这是问题 F 的第一个子任务。本子任务与第二个子任务的唯一区别在于对 $m$ 的约束条件以及时间限制。要成功 hack 本子任务，你必须同时解决这两个子任务。

宇宙中一共有 $n+1$ 种互不相同的颜色，编号为 $0$ 到 $n$。有一条长度为 $m$ 厘米的纸带，初始时整条纸带均被涂成颜色 $0$。

爱丽丝拿起画笔，按如下过程对纸带进行涂色：对每个 $i$ 从 $1$ 到 $n$（按此顺序），她选择两个整数 $0 \leq a_i < b_i \leq m$，使得区间 $[a_i, b_i]$ 当前恰好被涂成同一种颜色，并将该区间全部重绘为颜色 $i$。

爱丽丝所选的这些区间满足：纸带上每一厘米现在都被涂成了非 $0$ 的颜色。形式化地说，区间 $[i-1, i]$ 被涂成颜色 $c_i$（其中 $c_i \neq 0$）。除颜色 $0$ 外，其余每种颜色在纸带上均可见。

请计算能产生该最终配置的不同序列对 $\{a_i\}_{i=1}^n$、$\{b_i\}_{i=1}^n$ 的数量。

由于该数量可能很大，请输出其对 $998244353$ 取模的结果。

The first line contains a two integers $n$, $m$ ($1 \leq n \leq 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, \ldots, c_m$ ($1 \leq c_i \leq 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$.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 500$，且 $n = m$），分别表示除颜色 $0$ 外的颜色种数和纸条的长度。

第二行包含 $m$ 个以空格分隔的整数 $c_1, c_2, \ldots, c_m$（$1 \leq c_i \leq n$），表示操作结束后在区间 $[i-1, i]$ 上可见的颜色。保证对每个 $j$（$1 \leq j \leq n$），均存在下标 $k$ 使得 $c_k = j$。

注意：由于本子任务中 $n = m$，这意味着 $c$ 是 $1$ 到 $n$ 的一个排列。

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

输出一个整数——Alice 执行该涂色操作的方案数，对 $998244353$ 取模。

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.

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$.

在第一个例子中，共有 $5$ 种方案，如下图所示。其中，$0$ 表示白色，$1$ 表示红色，$2$ 表示绿色，$3$ 表示蓝色。

下面是一个无效的涂色过程示例：在第二步中，区间 $1\ 3$ 并非单色，因此不能被重新涂成颜色 $2$。