נתונה לך סדרה באורך $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)$.