Mex перестановки

Спочатку є масив $a$ з $n$ цілих чисел. Відомо, що всі його елементи знаходяться в діапазоні $[0;n-1]$ і вони попарно різні. Іншими словами, $a$ є перестановкою.

Позначимо $mex(S)$ як мінімальне невід'ємне ціле число, яке не належить множині $S$. Наприклад, $mex(\{1,2,3\})$ = $0$, $mex(\{0,1,3\})$ = $2$, $mex(\{0,1,2\})$ = $3$.

Масив $F$ будується таким чином, що $F_i$ = $mex(a_1,a_2,\dots ,a_{i-1},a_i)$. Позначимо $f(a)$ = $F$.

Досить легко побудувати масив $F$ за заданим масивом $a$, але на жаль, масив $a$ був втрачений. Ви хотіли відновити його за допомогою масиву $F$, але виявилося, що можливих масивів занадто багато. Ви хочете знати, скільки існує масивів $a$, таких що $f(a)$ = $F$ за модулем $998244353$.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^6$) — довжина перестановки.

Другий рядок містить $n$ цілих чисел $F_i$ ($0\le F_i\le n+1$) — елементи масиву $F$.

Вихідні дані

Виведіть одне ціле число — кількість масивів $a$, які задовольняють $f(a)$ = $F$ за модулем $998244353$.

Приклади

Оцінювання

1. ($3$ бали): $F_i=n+1$;

2. ($3$ бали): $F_i<F_{i+1}$ для всіх $i<n$;

3. ($5$ балів): $n\le 3$;

4. ($16$ балів): $n\le 7$;

5. ($18$ балів): $n\le 18$;

6. ($27$ балів): $n\le 1000$;

7. ($28$ балів): без додаткових обмежень.