Fişierul intrare/ieşire:	grigo.in, grigo.out	Sursă	Junior Challenge 2008
Autor	Adrian Airinei	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.05 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁, i₂ .. i_M si Grigo trebuie sa afle numarul de permutari distincte cu N elemente astfel incat numai pozitiile i₁, i₂ .. i_M sa fie vizibile. Ajutati-l pe Grigo afland restul impartirii acestui numar la 1 000 003.

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₁, i₂ .. i_M, care reprezinta pozitiile care trebuie sa fie vizibile.

Date de iesire

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

Restrictii

• 1 ≤ M ≤ N ≤ 100 000
• 1 ≤ i_j ≤ N, pentru orice j intre 1 si M

Exemplu

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.

Cum se trimit solutii?