D. Очередная задача на подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность целых чисел $$$a_1, a_2, \dots, a_k$$$ называется хорошим массивом, если $$$a_1 = k - 1$$$ и $$$a_1 > 0$$$. Например последовательности $$$[3, -1, 44, 0], [1, -99]$$$ — хорошие массивы, а последовательности $$$[3, 7, 8], [2, 5, 4, 1], [0]$$$ — нет.

Последовательность целых чисел называется хорошей, если она состоит из положительного количества подряд идущих хороших массивов. Например последовательности $$$[2, -3, 0, 1, 4]$$$, $$$[1, 2, 3, -3, -9, 4]$$$ — хорошие, а последовательности $$$[2, -3, 0, 1]$$$, $$$[1, 2, 3, -3 -9, 4, 1]$$$ — нет.

Для заданной последовательности чисел подсчитайте количество её подпоследовательностей, которые являются хорошими последовательностями, по модулю 998244353.

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

В первой строке задано число $$$n~(1 \le n \le 10^3)$$$ — длина изначальной последовательности. Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n~(-10^9 \le a_i \le 10^9)$$$ — сама последовательность.

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

В единственной строке выведите число — количество подпоследовательностей исходной последовательности, которые являются хорошими последовательностями, по модулю 998244353.

Примеры
Входные данные
3
2 1 1
Выходные данные
2
Входные данные
4
1 1 1 1
Выходные данные
7
Примечание

В первом тестовом примере две хорошие подпоследовательности — $$$[a_1, a_2, a_3]$$$ и $$$[a_2, a_3]$$$.

Во втором тестовом примере семь хороших подпоследовательностей — $$$[a_1, a_2, a_3, a_4], [a_1, a_2], [a_1, a_3], [a_1, a_4], [a_2, a_3], [a_2, a_4]$$$ и $$$[a_3, a_4]$$$.