תמורה היא סדרה באורך $n$ המורכבת ממספרים שלמים מ-$1$ עד $n$, שבה כל המספרים מופיעים בדיוק פעם אחת. לדוגמה, $[1]$, $[3, 5, 2, 1, 4]$ ו-$[1, 3, 2]$ הן תמורות, בעוד ש-$[2, 3, 2]$, $[4, 3, 1]$ ו-$[0]$ אינן תמורות.

נתון לך מערך $A_1, A_2, \dots, A_N$ המורכב מ-$N$ מספרים שלמים. כל מספר שלם הוא $0$ או $1$. מצא את מספר התמורות $P$ בגודל $N$ כך שהתנאים הבאים מתקיימים:

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

מכיוון שמספר התמורות הללו עשוי להיות גדול מאוד, הדפס את התשובה מודולו $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