Grigo

grigo

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

Grigo, un celebru personaj mioritic, a studiat recent la facultate teoria permutarilor. O permutare este un sir de $N$ numere naturale de la $1$ la $N$ astfel incat fiecare numar apare exact o singura data in sir. Pentru o permutare $P$ cu $N$ elemente spunem ca pozitia $i$ este _vizibila_ daca si numai daca $i=1$ sau $P{~j~}<P{~i~}$ pentru orice $j<i$. Buru ii furnizeaza lui Grigo o lista cu $M$ numere naturale distincte $i{~1~}, i{~2~} .. i{~M~}$ si Grigo trebuie sa afle numarul de permutari distincte cu $N$ elemente astfel incat numai pozitiile $i{~1~}, i{~2~} .. i{~M~}$ sa fie vizibile. Ajutati-l pe Grigo afland restul impartirii acestui numar la $1 000 003$.

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $grigo.in$ va contine pe prima linie numarele $N$ si $M$, separate printr-un singur spatiu, avand semnificatia din enunt. Pe a doua linie se afla $M$ numere naturale distincte $i{~1~}, i{~2~} .. i{~M~}$, care reprezinta pozitiile care trebuie sa fie vizibile.

Fisierul de intrare $grigo.in$ ...

h2. Date de iesire

Fisierul de iesire $grigo.out$ va contine un singur numar natural reprezentand raspunsul cautat de Grigo.

In fisierul de iesire $grigo.out$ ...

h2. Restrictii

* $1 ≤ M ≤ N ≤ 100 000$
* $1 ≤ i{~j~} ≤ N$, pentru orice $j$ intre $1$ si $M$

* $... ≤ ... ≤ ...$

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

| 4 2
  1 2
| 6

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

|
h3. Explicatie

Cele $6$ permutari valide sunt:
 
* $1 4 2 3$
* $1 4 3 2$
* $2 4 1 3$
* $2 4 3 1$
* $3 4 1 2$
* $3 4 2 1$.
 
Permutarea $1 2 3 4$ nu este valida deoarece si pozitiile $3$ si $4$ sunt vizibile.

...

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

3179