Fie N un număr natural nenul şi P o permutare de lungime N a numerelor din multimea {1, 2, ..., N}. Definim un element vizibil în permutarea P ca fiind un număr Pi care are proprietatea că Pj < Pi, 1 ≤ j < i sau i=1.

Cerinţă

Determinaţi numărul X de permutări de lungime N care au ca elemente vizibile exact M elemente date.

Date de intrare

Fişierul de intrare pviz.in conţine pe prima linie două numere naturale N şi M, cu semnificaţia din enunţ, separate printr-un spaţiu. A doua linie a fişierului conţine M numere naturale distincte, ordonate crescător, separate prin câte un spaţiu, reprezentând elementele vizibile.

Date de ieşire

Fişierul de ieşire pviz.out va conţine o singură linie pe care va fi scris un număr natural reprezentând restul împărţirii numărului X la 10007.

Restricţii

• 1 ≤ N ≤ 2000
• 1 ≤ M ≤ N
• Elementele vizibile sunt scrise în fişierul de intrare în ordine crescătoare.
• Pentru 10% din teste N ≤ 10
• Pentru 20% din teste N ≤ 14
• Pentru 60% din teste N ≤ 375

Exemple

pviz.in	pviz.out	Explicaţii
4 2 2 4	3	Sunt 3 permutări, de lungime 4, care au pe 2 şi 4 ca elemente vizibile: 2 4 3 1 2 4 1 3 2 1 4 3 Permutarea 2 3 4 1 nu corespunde cerinţei deoarece are ca elemente vizibile atât pe 2 şi 4, cât şi pe 3.

autor: Adrian Diaconu

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com