== include(page="template/taskheader" task_id="trotuar") ==
Un trotuar de lungime N şi lăţime L trebuie pavat cu dale. Dalele sunt de diferite tipuri, dar din fiecare tip avem o cantitate nelimitată. Lungimea dalelor în cazul fiecărui tip este aceeaşi L, iar lăţimea poate să fie o valoare dintre a1, a2, a3,... ak. Trotuarul are pe suprafaţa lui M zone ocupate, care nu vor fi pavate. Aceste zone au de fiecare dată o formă pătratică de latură 1 (reprezentând locul unor stâlpi, cutii poştale, canale, etc.). Se cunosc coordonatele acestor M puncte (x1,y1), (x2,y2),... (xm,ym). (x reprezintă coloana, y reprezintă linia punctului).
În exemplele de mai jos vedem trei metode distincte de acoperire a unui trotuar de dimensiuni 6*3 folosind două tipuri de dale: 1*3, respectiv 2*3, având trei zone ocupate pe trotuar, şi anume: (6,2), (3,1), (6,3).
Un trotuar de lungime $N$ şi lăţime $L$ trebuie pavat cu dale. Dalele sunt de diferite tipuri, dar din fiecare tip avem o cantitate nelimitată. Lungimea dalelor în cazul fiecărui tip este aceeaşi $L$, iar lăţimea poate să fie o valoare dintre $a{~1~}, a{~2~}, a{~3~},... a{~k~}$. Trotuarul are pe suprafaţa lui $M$ zone ocupate, care nu vor fi pavate. Aceste zone au de fiecare dată o formă pătratică de latură $1$ (reprezentând locul unor stâlpi, cutii poştale, canale, etc.). Se cunosc coordonatele acestor $M$ puncte $(x{~1~},y{~1~}), (x{~2~},y{~2~}),... (x{~m~},y{~m~})$. ( $x$ reprezintă coloana, $y$ reprezintă linia punctului).
În exemplele de mai jos vedem trei metode distincte de acoperire a unui trotuar de dimensiuni $6*3$ folosind două tipuri de dale: $1*3$, respectiv $2*3$, având trei zone ocupate pe trotuar, şi anume: $(6,2), (3,1), (6,3)$.
!problema/trotuar/?you_rock.jpg!
h2. Cerinţă
Cunoscând dimensiunea trotuarului, tipurile de dale disponibile, şi coordonatele zonelor ocupate, să se determine numărul de pavări distincte posibile modulo 666013.
Cunoscând dimensiunea trotuarului, tipurile de dale disponibile, şi coordonatele zonelor ocupate, să se determine numărul de pavări distincte posibile modulo $666013$.
h2. Date de intrare
Fişierul trotuar.in conţine pe prima linie 4 numere naturale N, L, K, şi M separate prin câte un spaţiu, reprezentând lungimea şi lăţimea trotuarului, respectiv numărul tipurilor de dale şi numărul zonelor ocupate. Pe linia următoare avem cele K lăţimi ale tipurilor de dale: a1, a2, a3,..., ak separate prin câte un spaţiu. Următoarele M linii conţin câte două numere naturale separate prin spaţiu, reprezentând câte o coordonată (xi,yi), pentru fiecare ale zonelor ocupate.
Fişierul $trotuar.in$ conţine pe prima linie $4$ numere naturale $N, L, K,$ şi $M$ separate prin câte un spaţiu, reprezentând lungimea şi lăţimea trotuarului, respectiv numărul tipurilor de dale şi numărul zonelor ocupate. Pe linia următoare avem cele $K$ lăţimi ale tipurilor de dale: $a{~1~}, a{~2~}, a{~3~},..., a{~k~}$ separate prin câte un spaţiu. Următoarele $M$ linii conţin câte două numere naturale separate prin spaţiu, reprezentând câte o coordonată $(x{~i~},y{~i~})$, pentru fiecare zona ocupata.
h2. Date de ieşire
Fişierul trotuar.out va conţine o singură linie, numărul pavărilor distincte modulo 666013.
Fişierul $trotuar.out$ va conţine o singură linie, numărul pavărilor distincte **modulo $666013$**.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 0 < N ≤ 100000
* 0 < K ≤ L ≤ 255
* 0 < a1, a2, a3,..., ak ≤ L sunt distincte două câte două
* 0 ≤ M ≤ 450
* Pentru 20% din teste M = 0
* $1 ≤ N ≤ 100000$
* $1 ≤ K ≤ L ≤ 255$
* $1 ≤ a{~1~}, a{~2~}, a{~3~},..., a{~k~} ≤ L$ sunt distincte două câte două
* $0 ≤ M ≤ 450$
* Pentru $20%$ din teste $M = 0$
* Se garantează existenţa a cel puţin unei soluţii
* Se recomandă folosirea întregilor pe 64 de biţi pentru operaţia de înmultire.
* Se recomandă folosirea întregilor pe $64$ de biţi pentru operaţia de înmultire.
h2. Exemplu
