codeforces#P1952E. Sweep Line

Sweep Line

Description

Be careful not to make a mistake. You might have to start all over again.
— Someone, probably

The first line contains one integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2$) — the array $a$.

Output a single integer — the number of solutions, modulo $20240401$.

Input

The first line contains one integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 2$) — the array $a$.

Output

Output a single integer — the number of solutions, modulo $20240401$.

7
1 1 2 1 1 2 0
7
1 1 2 1 1 1 0
7
0 1 2 1 1 1 0
1
2
0

Note

In the first sample, the array looks like this:

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

Obviously, the answer here is $1 \pmod{20240401}$.

In the second sample, the array looks like this:

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

I do not know why the answer here is $2 \pmod{20240401}$, I had to take a guess.

In the third sample, the array looks like this:

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

If the answer here is not $0 \pmod{20240401}$, I am literally going to explode.