Yana, Mino, White ו-Huzz הם החברים הכי טובים.
לאחר שסיים סוף-סוף את המשימות התובעניות של המאמן, Huzz הרוויח מנוחה. הוא מצא אותה באחר צהריים עצל אחד, שבו נראה היה שהעולם מאט לזחילה, עטוף באובך החמים והזהוב של הדמדומים המתקרבים. משב רוח עדין לא עשה הרבה מעבר להרעדת גרגרי האבק שרקדו בקרני השמש הנטויות מבעד לעליה של עץ אלון אדיר.
בתוך החלל המנמנם והנוח הזה, Huzz מצא תמורה בתוך בובת הכריש הרכה שלו. הוא החליט לשתף אותה עם חבריו לשם שעשוע.
Mino אוהב לפצל. הוא יכול לפצל את התמורה הזו למספר קטעים רציפים.
Yana אוהב להחליף. הוא יכול לבחור קטע רציף אחד ולהחליף בין האיבר המקסימלי והאיבר המינימלי שלו.
באופן ספציפי, הם יכולים לבצע את שני סוגי הפעולות הבאים מספר כלשהו של פעמים, בכל סדר:
- split: בחר קטע רציף אחד שאורכו גדול מ-$1$. לאחר מכן בחר מיקום בתוכו ופצל אותו לשני קטעים רציפים סמוכים. לדוגמה, ניתן לפצל את $(a_i, \dots, a_j)$ ל-$(a_i, \dots, a_k)$ ול-$(a_{k+1}, \dots, a_j)$, כאשר $i \le k < j$.
- swap: בחר קטע רציף אחד והחלף בין האיבר המקסימלי והאיבר המינימלי שלו.
לאחר ביצוע מספר כלשהו של פעולות הם מפסיקים, וכל הקטעים שהתקבלו ממוזגים בסדרם המקורי ליצירת תמורה חדשה.
White אוהבת לספור. היא תוהה — כמה תמורות שונות הם יכולים לקבל?
מאחר שהתוצאה עלולה להיות גדולה מאוד, עליך למצוא רק את התשובה מודולו $998\,244\,353$.
קלט
השורה הראשונה של הקלט מכילה מספר שלם $n$ ($1 \le n \le 500$), אורך התמורה.
השורה השנייה מכילה $n$ מספרים שלמים $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), המייצגים את התמורה עצמה. מובטח כי $\{a_n\}$ היא תמורה.
פלט
הדפס מספר שלם, מספר התמורות השונות שהם יכולים לקבל מודולו $998\,244\,353$.
דוגמאות
קלט
4 1 4 2 3
פלט
10
קלט
7 5 1 4 2 6 3 7
פלט
340
הערה
בדוגמה הראשונה, להלן כל התמורות האפשריות שהם יכולים לקבל:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$