E. Линейное сканирование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Будьте осторожны, чтобы не совершить ошибку. Вам, возможно, придется начать все сначала.
— Кто-то, вероятно
Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2$$$) — массив $$$a$$$.

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

Выведите одно целое число — количество решений по модулю $$$20240401$$$.

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

В первом примере массив выглядит следующим образом:

$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{gray}{0} $$$

Очевидно, что ответ здесь равен $$$1 \pmod{20240401}$$$.

Во втором примере массив выглядит следующим образом:

$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{gray}{0} $$$

Я не знаю, почему ответ здесь равен $$$2 \pmod{20240401}$$$, мне пришлось догадаться.

В третьем примере массив выглядит следующим образом:

$$$ \color{gray}{0} $$$$$$ \color{blue}{1} $$$$$$ \color{darkgreen}{2} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{blue}{1} $$$$$$ \color{gray}{0} $$$

Если ответ здесь не равен $$$0 \pmod{20240401}$$$, я буквально взорвусь.