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)$