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]

Difficulty: interview

Starter code:

Solutions:
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])

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]
    
    #print(i,j)
    if j==i+1 or i==j:
        return 1
    
    MININD=MININDLIST[i][j-1]

    #print(MININD)

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

    


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()

class SparseTable():
    """区間取得クエリをO(1)で答えるデータ構造をO(NlogN)で構築する
    query(l, r): 区間[l, r)に対するクエリに答える
    """
    def __init__(self, array, n):
        n = len(array)
        self.row_size = n.bit_length()

        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1

        # sparse_tableを構築する
        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):
        """区間[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 = list(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))