Дан двудольный граф с $n$ вершинами в каждой доле.

В этом графе каждая вершина из левой доли соединена с некоторым префиксом вершин из правой доли. А именно, $i$-я вершина в левой доле соединена с вершинами $1, 2, \dots, a_i$ в правой доле.

Найдите количество простых циклов в этом графе. Два цикла считаются различными, если существует ребро, которое присутствует в одном цикле, но отсутствует в другом.

Так как это число может быть большим, найдите его по модулю $998\,244\,353$.

Входные данные

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 5000$): количество вершин в каждой доле. Вторая строка входных данных содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): описание заданного графа.

Выходные данные

Выведите одно целое число: количество простых циклов в заданном графе по модулю $998\,244\,353$.

Примеры

Входные данные 1

1
1

Выходные данные 1

0

Входные данные 2

2
2 2

Выходные данные 2

1

Входные данные 3

3
3 3 2

Выходные данные 3

7

Входные данные 4

10
6 6 7 7 8 8 9 9 10 10

Выходные данные 4

410150080