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, \dots, 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), \dots (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 \cdot 3$ folosind două tipuri de dale: $1 \cdot 3$, respectiv $2 \cdot 3$, având trei zone ocupate pe trotuar, şi anume: $(6,2), (3,1), (6,3)$.

Cerință

Cunoscând dimensiunea trotuarului, tipurile de dale disponibile, şi coordonatele zonelor ocupate, să se determine numărul de pavări distincte posibile modulo $666 \ 013$.

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, \dots, 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 $1 \leq i \leq m$ ale zonelor ocupate.

Date de ieșire

Fişierul trotuar.out va conţine o singură linie, numărul pavărilor distincte modulo 666013.

Restricții și precizări

• $0 < N \leq 100 \ 000$
• $0 < K \leq L \leq 255$
• $0 < a_1, a_2, a_3, \dots, a_k \leq L$ sunt distincte două câte două
• $0 \leq M \leq 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.

Exemplu

trotuar.in

6 3 2 3
2 1
6 2
3 1
6 3

trotuar.out

4

Explicație

Sunt în total patru modalităţi distincte de a acoperi trotuarul. Trei dintre ele sunt cele din desenul de mai sus.