Yana、Mino、White、Huzz は親友です。
コーチの厳しい課題をついに終えた Huzz は、休息を手に入れました。ある気だるい午後、夕暮れが迫る暖かく黄金色の靄に包まれ、世界はゆっくりと歩みを緩めたかのようでした。そよ風は、大きなオークの木の葉の間から斜めに差し込む日差しの中で舞う塵をわずかに揺らすだけでした。
そんな眠気を誘う心地よい空白の中で、Huzz は柔らかいサメのぬいぐるみの中に順列を見つけました。彼は楽しみのためにそれを友人たちと共有することにしました。
Mino は分割が好きです。彼はこの順列をいくつかの連続する区間に分割することができます。
Yana は交換が好きです。彼は一つの連続する区間を選び、その最大要素と最小要素を交換することができます。
具体的には、彼らは以下の二種類の操作を任意の順序で何回でも行うことができます：
- split：長さが $1$ より大きい連続する区間を一つ選ぶ。次にその内部の位置を一つ選び、隣接する二つの連続する区間に分割する。例えば、$(a_i, \dots, a_j)$ は $(a_i, \dots, a_k)$ と $(a_{k+1}, \dots, a_j)$ に分割できる（ただし $i \le k < j$）。
- swap：連続する区間を一つ選び、その最大要素と最小要素を交換する。
任意の回数の操作を行った後、彼らは操作を終了し、得られたすべての区間を元の順序で結合して新しい順列を作ります。
White は数え上げが好きです。彼女は疑問に思いました——彼らは何通りの異なる順列を得ることができるのでしょうか？
答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りのみを求めてください。
入力
入力の最初の行には、順列の長さを表す整数 $n$（$1 \le n \le 500$）が与えられます。
二行目には、順列そのものを表す $n$ 個の整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le n$）が与えられます。$\{a_n\}$ が順列であることは保証されます。
出力
彼らが得ることのできる異なる順列の個数を $998\,244\,353$ で割った余りを表す整数を出力してください。
入出力例
入力
4 1 4 2 3
出力
10
入力
7 5 1 4 2 6 3 7
出力
340
注記
最初のサンプルにおいて、彼らが得ることのできるすべての順列は以下の通りです：
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$