순열이란 $1$부터 $n$까지의 정수로 이루어진 길이 $n$의 수열로, 모든 수가 정확히 한 번씩 등장하는 수열입니다. 예를 들어, $[1]$, $[3, 5, 2, 1, 4]$, $[1, 3, 2]$는 순열이지만, $[2, 3, 2]$, $[4, 3, 1]$, $[0]$은 순열이 아닙니다.

$N$개의 정수로 이루어진 배열 $A_1, A_2, \dots, A_N$이 주어집니다. 각 정수는 $0$ 또는 $1$입니다. 다음 조건을 만족하는 크기 $N$인 순열 $P$의 개수를 구하세요:

• $P_1 < P_2 > P_3 < P_4 \dots$
• 모든 ($1 \le i \le N$)에 대해, $A_{P_i} \equiv i \pmod 2$.

이러한 순열의 개수는 매우 클 수 있으므로, 답을 $998244353$으로 나눈 나머지를 출력하세요.

입력

첫째 줄에 정수 $N$ ($1 \le N \le 10^6$)이 주어집니다.

둘째 줄에 배열의 원소를 나타내는 공백으로 구분된 $N$개의 정수 $A_i$가 주어집니다. $A_i \in \{0, 1\}$임이 보장됩니다.

출력

조건을 만족하는 순열의 개수를 $998244353$으로 나눈 나머지를 한 줄에 출력합니다.

예제

예제 입력 1

2
1 0

예제 출력 1

1

예제 입력 2

1
0

예제 출력 2

0

예제 입력 3

7
1 1 0 1 0 1 0

예제 출력 3

8