Fişierul intrare/ieşire:	pviz.in, pviz.out	Sursă	ONI 2008, clasele 11-12
Autor	Adrian Diaconu	Adăugată de	Sima Cotizo •sima_cotizo
Timp execuţie pe test	0.025 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pviz

Fie N un numar natural nenul si P o permutare de lungime N a numerelor din multimea {1, 2, ..., N}. Definim un element vizibil in permutarea P ca fiind un numar P_i care are proprietatea ca P_j < P_i, oricare ar fi 1 ≤ j < i sau i=1.

Determinati numarul X de permutari de lungime N care au ca elemente vizibile exact M elemente date.

Date de intrare

Fisierul de intrare pviz.in contine pe prima linie doua numere naturale N si M, cu semnificatia din enunt, separate printr-un spatiu. A doua linie a fisierului contine M numere naturale distincte, ordonate crescator, separate prin cate un spatiu, reprezentand elementele vizibile.

Date de iesire

In fisierul de iesire pviz.out va contine o singura linie pe care va fi scris un numar natural reprezentand restul impartirii numarului X la 10 007.

Restrictii

• 1 ≤ N ≤ 2000
• 1 ≤ M ≤ N
• Elementele vizibile sunt scrise in fisierul de intrare in ordine crescatoare.
• Pentru 10% din teste N ≤ 10
• Pentru 20% din teste N ≤ 14
• Pentru 60% din teste N ≤ 375

Exemplu

Explicatie

Sunt 3 permutari, de lungime 4, care au pe 2 si 4 ca elemente vizibile:
2 4 3 1
2 4 1 3
2 1 4 3
Permutarea 2 3 4 1 nu corespunde cerintei deoarece are ca elemente vizibile atat pe 2 si 4 cat si pe 3.

Cum se trimit solutii?