pviz

Pviz

== include(page="template/taskheader" task_id="pviz") ==

Poveste si cerinta...

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 &le; j < i$ sau $i=1$.
 
Determinati numarul $X$ de permutari de lungime $N$ care au ca elemente vizibile exact $M$ elemente date.

h2. Date de intrare

Fisierul de intrare $pviz.in$ ...

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.

h2. Date de iesire

In fisierul de iesire $pviz.out$ ...

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

h2. 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$

h2. Exemplu
table(example). |_. pviz.in |_. pviz.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2
2 4
| 3

|
h3. 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$.

== include(page="template/taskfooter" task_id="pviz") ==

3080