Dany jest graf dwudzielny z $n$ wierzchołkami w każdej z części.

W tym grafie każdy wierzchołek z lewej części jest połączony z pewnym prefiksem wierzchołków z prawej części. Mianowicie, $i$-ty wierzchołek w lewej części jest połączony z wierzchołkami $1, 2, \dots, a_i$ w prawej części.

Znajdź liczbę prostych cykli w tym grafie. Dwa cykle są różne, jeśli istnieje krawędź, która występuje w jednym cyklu, a nie występuje w drugim.

Ponieważ liczba ta może być duża, podaj wynik modulo $998\,244\,353$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 5000$): liczbę wierzchołków w każdej z części.

Druga linia wejścia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): opis danego grafu.

Wyjście

Wypisz jedną liczbę całkowitą: liczbę prostych cykli w danym grafie, modulo $998\,244\,353$.

Przykład

Wejście 1

1
1

Wyjście 1

0

Wejście 2

2
2 2

Wyjście 2

1

Wejście 3

3
3 3 2

Wyjście 3

7

Wejście 4

10
6 6 7 7 8 8 9 9 10 10

Wyjście 4

410150080