pviz

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 $P_i$ care are proprietatea că $P_j < P_i$, 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 şi precizări

• 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

Exemplu

pviz.in

4 2
2 4

pviz.out

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.