กำหนดลำดับความยาว $N$ คือ $A = (A_1, A_2, \dots, A_N)$ สำหรับลำดับ $A$ นี้ ให้ดำเนินการต่อไปนี้ตามลำดับสำหรับ $i = 1, 2, \dots, N - 1$:
- สลับค่า $A_i$ กับ $A_{i+1}$ หรือไม่ทำอะไรเลย
จงหาจำนวนของลำดับที่แตกต่างกันที่สามารถเกิดขึ้นได้หลังจากการดำเนินการเหล่านี้ มอดุโล $998244353$
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะถูกกำหนดให้ในรูปแบบต่อไปนี้:
$$\begin{aligned} &N \\ &A_1 \ A_2 \ \dots \ A_N \end{aligned}$$
- ข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $1 \le N \le 10^6$
- $1 \le A_i \le N$
ข้อมูลส่งออก
พิมพ์คำตอบในบรรทัดเดียว
ตัวอย่าง
ข้อมูลนำเข้า 1
5 1 2 1 2 3
ข้อมูลส่งออก 1
10
ข้อมูลนำเข้า 2
9 3 1 6 2 2 7 7 6 6
ข้อมูลส่งออก 2
104
หมายเหตุ
ในตัวอย่างแรก มีลำดับที่เป็นไปได้ $10$ แบบที่สามารถเกิดขึ้นได้หลังจากการดำเนินการ ลำดับเหล่านี้ได้แก่:
- $(1, 2, 1, 2, 3)$,
- $(1, 2, 1, 3, 2)$,
- $(1, 2, 2, 1, 3)$,
- $(1, 2, 2, 3, 1)$,
- $(1, 1, 2, 2, 3)$,
- $(1, 1, 2, 3, 2)$,
- $(2, 1, 1, 2, 3)$,
- $(2, 1, 1, 3, 2)$,
- $(2, 1, 2, 1, 3)$,
- $(2, 1, 2, 3, 1)$.