#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 nn (1n1051 \leq n \leq 10^5) — the length of the array aa.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai20 \leq a_i \leq 2) — the array aa.

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

Input

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

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (0ai20 \leq a_i \leq 2) — the array aa.

Output

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

样例输入 1

7
1 1 2 1 1 2 0

样例输出 1

1

样例输入 2

7
1 1 2 1 1 1 0

样例输出 2

2

样例输入 3

7
0 1 2 1 1 1 0

样例输出 3

0

Note

In the first sample, the array looks like this:

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

Obviously, the answer here is 1(mod20240401)1 \pmod{20240401}.

In the second sample, the array looks like this:

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

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

In the third sample, the array looks like this:

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

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