Vous disposez d'un graphe biparti avec $n$ sommets dans chaque partie.

Dans ce graphe, chaque sommet de la partie gauche est relié à un certain préfixe de sommets de la partie droite. Plus précisément, le $i$-ième sommet de la partie gauche est relié aux sommets $1, 2, \dots, a_i$ de la partie droite.

Trouvez le nombre de cycles simples (sans répétition de sommets) dans ce graphe. Deux cycles sont considérés comme différents s'il existe une arête présente dans l'un mais pas dans l'autre.

Comme ce nombre peut être grand, donnez le résultat modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 5000$) : le nombre de sommets dans chaque partie.

La ligne suivante contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) : une description du graphe donné.

Sortie

Affichez un entier : le nombre de cycles simples dans le graphe donné, modulo $998\,244\,353$.

Exemples

Entrée 1

1
1

Sortie 1

0

Entrée 2

2
2 2

Sortie 2

1

Entrée 3

3
3 3 2

Sortie 3

7

Entrée 4

10
6 6 7 7 8 8 9 9 10 10

Sortie 4

410150080