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