Yana, Mino, White, and Huzz are best friends.
Having finally finished the coach's demanding tasks, Huzz had earned a rest. He found it on one lazy afternoon, where the world seemed to slow to a crawl, wrapped in the warm, golden haze of impending dusk. A gentle breeze did little more than stir the dust motes dancing in the sunbeams slanting through the leaves of a great oak tree.
In that sleepy, comfortable void, Huzz found a permutation in his soft shark toy. He decided to share it with his friends for fun.
Mino loves splitting. He can split this permutation into several contiguous segments.
Yana loves swapping. He can choose one contiguous segment and swap its maximum and minimum elements.
Specifically, they can perform the following two types of operations any number of times, in any order:
- split: Choose one contiguous segment whose length is greater than $1$. Then choose a position inside it and split it into two adjacent contiguous segments. For example, $(a_i, \dots, a_j)$ can be split into $(a_i, \dots, a_k)$ and $(a_{k+1}, \dots, a_j)$, where $i \le k < j$.
- swap: Choose one contiguous segment and swap its maximum and minimum elements.
After performing any number of operations, they stop performing, and all resulting segments are merged in their original order to form a new permutation.
White loves counting. She wonders — how many distinct permutations can they obtain?
As the result can be very large, you only need to find the answer modulo $998\,244\,353$.
Input
The first line of the input contains an integer $n$ ($1 \le n \le 500$), the length of the permutation.
The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), representing the permutation itself. It's guaranteed that $\{a_n\}$ is a permutation.
Output
Print an integer, the number of distinct permutations they can obtain modulo $998\,244\,353$.
Examples
input
4 1 4 2 3
output
10
input
7 5 1 4 2 6 3 7
output
340
Note
In the first sample, the following are all possible permutations they can obtain:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$