التبديل هو متتالية طولها $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