Một hoán vị là một dãy có độ dài $n$ gồm các số nguyên từ $1$ đến $n$, trong đó tất cả các số xuất hiện đúng một lần. Ví dụ, $[1]$, $[3, 5, 2, 1, 4]$ và $[1, 3, 2]$ là các hoán vị, trong khi $[2, 3, 2]$, $[4, 3, 1]$ và $[0]$ thì không.

Bạn được cho một mảng $A_1, A_2, \dots, A_N$ gồm $N$ số nguyên. Mỗi số nguyên là $0$ hoặc $1$. Hãy tìm số lượng hoán vị $P$ kích thước $N$ sao cho các điều kiện sau được thỏa mãn:

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

Vì số lượng hoán vị như vậy có thể rất lớn, hãy in ra đáp án theo modulo $998244353$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ ($1 \le N \le 10^6$).

Dòng thứ hai chứa $N$ số nguyên $A_i$ cách nhau bởi dấu cách — các phần tử của mảng. Đảm bảo rằng $A_i \in \{0, 1\}$.

Dữ liệu ra

In ra một dòng duy nhất chứa số lượng hoán vị thỏa mãn điều kiện theo modulo $998244353$.

Ví dụ

Dữ liệu vào 1

2
1 0

Dữ liệu ra 1

1

Dữ liệu vào 2

1
0

Dữ liệu ra 2

0

Dữ liệu vào 3

7
1 1 0 1 0 1 0

Dữ liệu ra 3

8