While creating problems, Kyoya Kanan often needs to construct long sequences.

One day, she came up with a method to construct a sequence of length $O(n \times n!)$ from a permutation of length $n$: Given a permutation $P$ of length $n$, let $m$ be the number of permutations of length $n$ that are lexicographically less than or equal to $P$. Let these permutations be $P_1, \dots, P_m$ in lexicographical order. The sequence $S(P)$ constructed from $P$ is defined as $P_{1,1}, \dots, P_{1,n}, P_{2,1}, \dots, P_{m,n}$, which has a length of $n \times m$.

For example, if $P=[2,1,3]$, the permutations of length $3$ that are lexicographically less than or equal to it are $[1,2,3], [1,3,2], [2,1,3]$. Thus, $S(P)=[1,2,3,1,3,2,2,1,3]$.

Given a permutation $P$ of length $n$, Kanan wants you to calculate the number of distinct subsequences of $S(P)$ (including the empty subsequence).

A sequence $t$ is a subsequence of $s$ if and only if $t$ can be obtained by deleting some (possibly zero or all) characters from $s$.

Two sequences $t_1$ and $t_2$ are distinct if and only if they have different lengths or there exists an index where the elements differ.

Input

The first line contains a positive integer $n$ ($1 \leq n \leq 50$).

The second line contains a permutation $P_1, \dots, P_n$ of length $n$ ($1 \leq P_i \leq n$).

Output

Output a single integer representing the answer. Since the answer may be very large, output it modulo $998244353$.

Examples

Input 1

2
2 1

Output 1

11

Input 2

3
3 1 2

Output 2

8703

Input 3

8
8 1 7 2 6 3 5 4

Output 3

644319900

Subtasks

Subtask 1 (21 points): $n \leq 8$.

Subtask 2 (47 points): $P_i = n-i+1$.

Subtask 3 (32 points): No special restrictions.