Une permutation est une séquence de longueur $n$ composée d'entiers de $1$ à $n$, dans laquelle tous les nombres apparaissent exactement une fois. Par exemple, $[1]$, $[3, 5, 2, 1, 4]$ et $[1, 3, 2]$ sont des permutations, tandis que $[2, 3, 2]$, $[4, 3, 1]$ et $[0]$ n'en sont pas.
On vous donne un tableau $A_1, A_2, \dots, A_N$ composé de $N$ entiers. Chaque entier vaut $0$ ou $1$. Trouvez le nombre de permutations $P$ de taille $N$ telles que les conditions suivantes soient vérifiées :
- $P_1 < P_2 > P_3 < P_4 \dots$
- $A_{P_i} \equiv i \pmod 2$, pour tout ($1 \le i \le N$).
Comme le nombre de ces permutations peut être très grand, affichez la réponse modulo $998244353$.
Entrée
La première ligne contient un entier $N$ ($1 \le N \le 10^6$).
La deuxième ligne contient $N$ entiers $A_i$ séparés par des espaces — les éléments du tableau. Il est garanti que $A_i \in \{0, 1\}$.
Sortie
Affichez une seule ligne contenant le nombre de permutations satisfaisant les conditions modulo $998244353$.
Exemples
Exemple d'entrée 1
2 1 0
Exemple de sortie 1
1
Exemple d'entrée 2
1 0
Exemple de sortie 2
0
Exemple d'entrée 3
7 1 1 0 1 0 1 0
Exemple de sortie 3
8