Permutasi adalah barisan sepanjang $n$ yang terdiri dari bilangan bulat dari $1$ hingga $n$, di mana semua bilangan muncul tepat satu kali. Sebagai contoh, $[1]$, $[3, 5, 2, 1, 4]$, dan $[1, 3, 2]$ adalah permutasi, sedangkan $[2, 3, 2]$, $[4, 3, 1]$, dan $[0]$ bukan.

Anda diberikan sebuah larik $A_1, A_2, \dots, A_N$ yang terdiri dari $N$ bilangan bulat. Setiap bilangan bulat bernilai $0$ atau $1$. Carilah banyaknya permutasi $P$ berukuran $N$ sedemikian sehingga syarat-syarat berikut terpenuhi:

• $P_1 < P_2 > P_3 < P_4 \dots$
• $A_{P_i} \equiv i \pmod 2$, untuk semua ($1 \le i \le N$).

Karena banyaknya permutasi tersebut bisa sangat besar, cetaklah jawabannya modulo $998244353$.

Masukan

Baris pertama berisi sebuah bilangan bulat $N$ ($1 \le N \le 10^6$).

Baris kedua berisi $N$ bilangan bulat $A_i$ yang dipisahkan spasi — elemen-elemen larik. Dijamin bahwa $A_i \in \{0, 1\}$.

Keluaran

Keluarkan satu baris yang berisi banyaknya permutasi yang memenuhi syarat modulo $998244353$.

Contoh

Contoh Masukan 1

2
1 0

Contoh Keluaran 1

1

Contoh Masukan 2

1
0

Contoh Keluaran 2

0

Contoh Masukan 3

7
1 1 0 1 0 1 0

Contoh Keluaran 3

8