Yana, Mino, White et Huzz sont meilleurs amis.

Ayant enfin terminé les tâches exigeantes de l'entraîneur, Huzz avait bien mérité un peu de repos. Il l'a trouvé lors d'un après-midi paresseux, où le monde semblait tourner au ralenti, enveloppé dans la brume chaude et dorée du crépuscule imminent. Une douce brise faisait à peine plus que soulever les grains de poussière dansant dans les rayons de soleil obliques filtrant à travers les feuilles d'un grand chêne.

Dans ce vide confortable et assoupissant, Huzz a trouvé une permutation dans sa peluche de requin toute douce. Il a décidé de la partager avec ses amis pour s'amuser.

Mino adore découper. Il peut découper cette permutation en plusieurs segments contigus.

Yana adore échanger. Il peut choisir un segment contigu et échanger son élément maximum et son élément minimum.

Plus précisément, ils peuvent effectuer les deux types d'opérations suivants un nombre quelconque de fois, dans n'importe quel ordre :

• split : Choisir un segment contigu dont la longueur est strictement supérieure à $1$. Choisir ensuite une position à l'intérieur de celui-ci et le découper en deux segments contigus adjacents. Par exemple, $(a_i, \dots, a_j)$ peut être découpé en $(a_i, \dots, a_k)$ et $(a_{k+1}, \dots, a_j)$, où $i \le k < j$.
• swap : Choisir un segment contigu et échanger ses éléments maximum et minimum.

Après avoir effectué un nombre quelconque d'opérations, ils s'arrêtent, et tous les segments obtenus sont fusionnés dans leur ordre d'origine pour former une nouvelle permutation.

White adore compter. Elle se demande — combien de permutations distinctes peuvent-ils obtenir ?

Comme le résultat peut être très grand, il vous suffit de trouver la réponse modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 500$), la longueur de la permutation.

La deuxième ligne contient $n$ entiers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), représentant la permutation elle-même. Il est garanti que $\{a_n\}$ est une permutation.

Sortie

Affichez un entier, le nombre de permutations distinctes qu'ils peuvent obtenir modulo $998\,244\,353$.

Exemples

Entrée

4
1 4 2 3

Sortie

10

Entrée

7
5 1 4 2 6 3 7

Sortie

340

Note

Dans le premier exemple, voici toutes les permutations possibles qu'ils peuvent obtenir :

$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$