O permutare cu N elemente este un șir a[1], a[2], …, a[N] care conține toate numerele naturale 1, 2, …, N, fiecare număr exact o dată. Un exemplu de permutare cu 6 elemente poate fi următorul șir: [3, 1, 6, 4, 5, 2].

Despre o permutare vom spune că este de tip munte, dacă printre cele N elemente ale sale există un element de indice M astfel încât 1 < M < N, secvența formată din primele M elemente este strict crescătoare, iar secvența formată din ultimele N–M+1 elemente este strict descrescătoare. Adică, folosind notația matematică, avem a[1] < a[2] < ... < a[M - 1] < a[M] > a[M+1] > ... > a[N]. Un exemplu de munte cu 6 elemente poate fi următorul șir: [1, 2, 4, 5, 6, 3].

În problema noastră vom considera că avem o permutare cu N elemente indexate de la 1 la N. Asupra elementelor permutării putem aplica două tipuri de operații de interschimbare simetrică:

• swap(P, N-P+1) – în permutarea a se interschimbă elementele de pe pozițiile P si N-P+1, egal distanțate de cele două margini ale permutării. Operația necesită 1 ≤ P ≤ N și P ≠ N-P+1.
• dswap(P, Q, N-P+1, N-Q+1) – în permutarea a se interschimbă simultan două perechi de elemente. Se vor interschimba simultan elementele de pe pozițiile P și Q, respectiv elementele de pe pozițiile N-P+1 și N-Q+1. Operația se poate aplica dacă și numai dacă toate cele patru poziții sunt distincte două câte două. Cu alte cuvinte, operația necesită 1 ≤ P, Q ≤ N și mulțimea {P, Q, N-P+1, N-Q+1} să aibă cardinal patru.

Plecând de la permutarea noastră și aplicând succesiv operații de ambele tipuri, unde fiecare tip poate fi folosit de zero sau mai multe ori, se poate obține o gamă variată de permutări.

Cerința

• Să se precizeze dacă pentru permutarea dată aplicând oricâte operații de swap sau dswap se poate obține o permutare de tip munte.
• Plecând de la permutarea dată, câte permutări de tip munte distincte se pot obține aplicând oricâte operații de swap sau dswap?

Date de intrare

Fișierul de intrare munte.in conține pe prima linie două numere naturale C ∈ {1, 2} și N, reprezentând cerința care trebuie rezolvată, respectiv numărul de elemente ale permutării a. Pe a doua linie se găsesc N numere naturale separate prin câte un singur spațiu, reprezentând permutarea a.

Date de ieșire

Fișierul de ieșire munte.out va conține o singură linie, în funcție de cerință:

• pentru C = 1, în cazul în care se poate obține cel puțin o permutare de tip munte plecând de la șirul a se va afișa cuvântul DA, altfel cuvântul NU;
• pentru C = 2, se va afișa un singur număr natural, reprezentând numărul permutărilor de tip munte distincte ce se pot obține aplicând doar operații de swap și dswap asupra permutării citite. Întrucât această valoare poate fi foarte mare, se va tipări rezultatul modulo 111.181.111.

Restricții și precizări

• C ∈ {1, 2}
• 4 ≤ N ≤ 200.000

Exemplul 1:

munte.in

2 7
3 4 2 7 1 6 5

munte.out

4

Explicație

Se pot obține următoarele patru permutări de tip munte:
1 3 4 7 6 5 2
2 3 4 7 6 5 1
2 5 6 7 4 3 1
1 5 6 7 4 3 2

Exemplul 2:

munte.in

1 6
6 3 4 5 1 2

munte.out

DA

Explicație

Se pot obține următoarele permutări de tip munte:
1 2 4 5 6 3
3 6 5 4 2 1

Exemplul 3:

munte.in

1 6
1 2 3 5 4 6

munte.out

NU

Explicație

Nu există niciun mod de a transforma permutarea în munte.

Exemplul 4:

munte.in

1 7
2 3 4 1 7 6 5

munte.out

NU

Explicație

Nu există niciun mod de a transforma permutarea în munte.