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


-----Input-----

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


-----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]

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Graph traversal


Solutions:
class SparseTable:

	def __init__(self, array, n):
		n = len(array)
		self.row_size = n.bit_length()
		self.log_table = [0] * (n + 1)
		for i in range(2, n + 1):
			self.log_table[i] = self.log_table[i // 2] + 1
		self.sparse_table = [[0] * n for _ in range(self.row_size)]
		for i in range(n):
			self.sparse_table[0][i] = array[i]
		for row in range(1, self.row_size):
			for i in range(n - (1 << row) + 1):
				self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], self.sparse_table[row - 1][i + (1 << row - 1)])

	def _merge(self, num1, num2):
		return min(num1, num2)

	def query(self, l, r):
		row = self.log_table[r - l]
		return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
sp = SparseTable(a, n)
to_ind = {}
for i in range(n):
	to_ind[a[i]] = i
dp = [[-1] * (n + 1) for i in range(n + 1)]

def solve(l, r):
	if dp[l][r] != -1:
		return dp[l][r]
	if l == r:
		dp[l][r] = 1
		return 1
	if r - l == 1:
		dp[l][r] = 1
		return 1
	ind = to_ind[sp.query(l, r)]
	res1 = 0
	res2 = 0
	for i in range(ind + 1, r + 1):
		res1 += solve(ind + 1, i) * solve(i, r)
		res1 %= MOD
	for i in range(l, ind + 1):
		res2 += solve(l, i) * solve(i, ind)
		res2 %= MOD
	dp[l][r] = max(res1, 1) * max(res2, 1)
	dp[l][r] %= MOD
	return dp[l][r]
print(solve(0, n) % MOD)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
(n, m) = li()
l = li()
l = [i - 1 for i in l]
mintill = [[0] * m for i in range(m)]
for i in range(n):
	curr = l[i]
	an = i
	for j in range(i + 1, m):
		if l[j] < curr:
			curr = l[j]
			an = j
		mintill[i][j] = an
score = [[-1] * (m + 1) for i in range(m + 1)]

def recursive(i, j):
	if score[i][j] != -1:
		return score[i][j]
	if i == j or i + 1 == j:
		return 1
	mincurr = mintill[i][j - 1]
	left = right = 0
	for k in range(i, mincurr + 1):
		left = (left + recursive(i, k) * recursive(k, mincurr)) % mod
	for k in range(mincurr + 1, j + 1):
		right = (right + recursive(mincurr + 1, k) * recursive(k, j)) % mod
	score[i][j] = left * right % mod
	return score[i][j]
print(recursive(0, m))


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a - 1 for a in A]
MININDLIST = [[i] * m for i in range(m)]
for i in range(m):
	MIN = A[i]
	MININDNOW = i
	for j in range(i, m):
		if A[j] < MIN:
			MIN = A[j]
			MININDNOW = j
		MININDLIST[i][j] = MININDNOW
mod = 998244353
SCORE = [0] * (m + 1) ** 2

def calc(i, j, m):
	if SCORE[i * (m + 1) + j] != 0:
		return SCORE[i * (m + 1) + j]
	if j == i + 1 or i == j:
		return 1
	MININD = MININDLIST[i][j - 1]
	ANS1 = ANS2 = 0
	for mi in range(i, MININD + 1):
		ANS1 = (ANS1 + calc(i, mi, m) * calc(mi, MININD, m)) % mod
	for Mi in range(MININD + 1, j + 1):
		ANS2 = (ANS2 + calc(MININD + 1, Mi, m) * calc(Mi, j, m)) % mod
	SCORE[i * (m + 1) + j] = ANS1 * ANS2 % mod
	return SCORE[i * (m + 1) + j]
print(calc(0, m, m))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
index = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	mini = 10000000000000
	for j in range(i, n):
		if l[j] < mini:
			inde = j
			mini = l[j]
		index[i][j] = inde
prime = 998244353
d = {}
val = [[1 for i in range(n + 1)] for j in range(n + 1)]
for i in range(n):
	for j in range(n - i):
		if i == 0:
			val[j][j + i] = 1
		elif i == 1:
			val[j][j + i] = 2
		else:
			ind = index[j][j + i]
			sumap = 0
			sumak = 0
			for p in range(j, ind + 1):
				sumap += val[j][p - 1] * val[p][ind - 1] % prime
			for k in range(ind, j + i + 1):
				sumak += val[ind + 1][k] * val[k + 1][j + i] % prime
			val[j][j + i] = sumap * sumak % prime
print(val[0][n - 1])


def main():
	line = input().split()
	n = int(line[0])
	line = input().split()
	v = [int(x) for x in line]
	mod = 998244353
	dp = [[1] * (n + 5) for i in range(n + 5)]
	for sz in range(2, n + 1):
		for lo in range(1, n - sz + 2):
			hi = lo + sz - 1
			(pos, num) = (-1, n + 5)
			for k in range(lo, hi + 1):
				if v[k - 1] < num:
					num = v[k - 1]
					pos = k
			(s1, s2) = (0, 0)
			for k in range(lo, pos + 1):
				cnt = dp[lo][k - 1] * dp[k][pos - 1] % mod
				s1 = (s1 + cnt) % mod
			for k in range(pos, hi + 1):
				cnt = dp[pos + 1][k] * dp[k + 1][hi] % mod
				s2 = (s2 + cnt) % mod
			dp[lo][hi] = s1 * s2 % mod
	print(dp[1][n])
main()