== 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 $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!
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).
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: $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.
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.
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
* $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$
* $... ≤ ... ≤ ...$
* 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
* 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
