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

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

h2. Date de intrare