การเรียงสับเปลี่ยนคือลำดับที่มีความยาว $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$)

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $A_i$ จำนวน $N$ ตัวที่คั่นด้วยช่องว่าง — สมาชิกของอาร์เรย์ รับประกันว่า $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