Fişierul intrare/ieşire:grigo.in, grigo.outSursăJunior Challenge 2008
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.05 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/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 Pj<Pi pentru orice j<i. Buru ii furnizeaza lui Grigo o lista cu M numere naturale distincte i1, i2 .. iM si Grigo trebuie sa afle numarul de permutari distincte cu N elemente astfel incat numai pozitiile i1, i2 .. iM 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 i1, i2 .. iM, 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 ≤ ij ≤ N, pentru orice j intre 1 si M

Exemplu

grigo.ingrigo.out
4 2
1 2
6

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content