Digits

În urma succesului lor regional (în curând și internațional), Los Patrons (echipă formată din Gustavo, Alfredo și Estefano) au adunat o sumă considerabilă de bani, astfel încât se împiedică de ei în viața de zi cu zi. Alfredo a găsit două teancuri mari de bani (unul în buzunarul stâng, iar celălalt în buzunarul drept), astfel că le-a împărțit celor doi colegi pentru a le număra, urmând ca aceștia să îi spună suma totală. Estefano și Gustavo s-au gândit să îi dea o nouă provocare: aflarea numărului de perechi de valori ale celor două teancuri inițiale posibile.

Pentru aceasta, ei îi vor spune o bază arbitrară B, suma totală de bani în baza B (și numărul de cifre al acestei sume în această bază), pe lângă M proprietăți suplimentare ale cifrelor valorilor (în baza B) celor două teancuri inițiale. Fie a și b valoarea primului, respectiv celui de-al doilea teanc. Proprietățile suplimentare sunt de tipul $a_i + b_j = k$, $a_i − b_j = k$, unde k este o constantă (posibil diferită pentru fiecare proprietate), iar $a_0, .. , a_{N−1}$ și $b_0, ... , b_{N−1}$ sunt cifrele celor două valori, unde $a_0$ și $b_0$ sunt cele mai nesemnificative, iar $a_{N−1}$ si $b_{N−1}$ sunt cele mai semnificative.

Alfredo a rezolvat această problemă destul de repede, așa că vă provoacă (la rândul lui) și pe voi să o rezolvați. Știind că răspunsul poate fi foarte mare, este suficient să aflați doar restul împărțirii acestuia la $10^9 + 7$.

Date de intrare

Pe prima linie se găsec 3 numere întregi N, M, B, reprezentând numărul de cifre ale valorilor celor 2 teancuri (și al sumei acestor valori), numărul de restricții dintre cifre, și baza de numerație. Pe a doua linie, se află, separate prin spații, cifrele sumei, de la cea mai semnificativă la cea mai nesemnificativă. Pe următoarele M linii se află restricțiile care sunt fie de forma i + j k cu semnificația ca $a_i + b_j = k$, fie de forma i − j k reprezentând $a_i − b_j = k$.

Date de ieșire

Se va afișa o singură linie, ce conține un singur număr întreg, reprezentând numărul de perechi posibile modulo $10^9 + 7$.

Restricții și precizări

• 1 ≤ N ≤ 18
• 1 ≤ M ≤ 70
• 2 ≤ B ≤ 10 000 000
• Atât cele 2 valori cât și suma lor au exact N cifre (cea mai semnificativă cifră din fiecare număr este nenulă).
• A fost adăugat un test suplimentar

Subtask 1 (7 puncte)

• 1 ≤ N ≤ 18, M = 0, B ≤ 30

Subtask 2 (8 puncte)

• 1 ≤ N ≤ 6, B = 10

Subtask 3 (20 puncte)

• $1 ≤ N ≤ 18, c_i = B − 1$ pentru fiecare 0 ≤ i < N și B ≤ 30

Subtask 4 (13 puncte)

• 1 ≤ N ≤ 18, B ≤ 100
• Toate restricțiile sunt intre cifre de forma $a_i$ și $b_i$.

Subtask 5 (18 puncte)

• 1 ≤ N ≤ 18, B ≤ 30
• Toate restricțiile sunt de forma $a_i + b_j = k$ (nu avem restricții cu −).

Subtask 6 (11 puncte)

• 1 ≤ N ≤ 18, B ≤ 30.

Subtask 7 (23 puncte)

• Fără restricții suplimentare.

Exemplu

stdin

5 4 20
10 10 10 12 10
3 + 1 10
4 + 1 10
4 - 4 0
0 + 2 10

stdout

11

stdin

2 2 20
10 10
1 + 0 12
1 - 0 0

stdout

1

stdin

2 1 20
10 10
1 + 0 12

stdout

9

stdin

3 1 20
8 10 10
0 - 0 -2

stdout

261

stdin

3 1 20
10 10 8
0 - 0 -2

stdout

341

Explicații

În această explicație, un număr în baza B cu cifrele $a_k, ... , a_0$, unde $a_k$ este cea mai semnificativă, și $a_0$ cea mai nesimnificativă, se notează cu $[a_k, ... , a_0]$.

Pentru primul exemplu:

1. [5, 5, 0, 7, 0] + [5, 5, 10, 5, 10];
2. [5, 5, 1, 7, 1] + [5, 5, 9, 5, 9];
3. [5, 5, 2, 7, 2] + [5, 5, 8, 5, 8];
4. [5, 5, 3, 7, 3] + [5, 5, 7, 5, 7];
5. [5, 5, 4, 7, 4] + [5, 5, 6, 5, 6];
6. [5, 5, 5, 7, 5] + [5, 5, 5, 5, 5];
7. [5, 5, 6, 7, 6] + [5, 5, 4, 5, 4];
8. [5, 5, 7, 7, 7] + [5, 5, 3, 5, 3];
9. [5, 5, 8, 7, 8] + [5, 5, 2, 5, 2];
10. [5, 5, 9, 7, 9] + [5, 5, 1, 5, 1];
11. [5, 5, 10, 7, 10] + [5, 5, 0, 5, 0].

Pentru al doilea exemplu:

1. [6, 4] + [4, 6].

Pentru al treilea exemplu:

1. [2, 0] + [8, 10];
2. [3, 1] + [7, 9];
3. [4, 2] + [6, 8];
4. [5, 3] + [5, 7];
5. [6, 4] + [4, 6];
6. [7, 5] + [3, 5];
7. [8, 6] + [2, 4];
8. [9, 7] + [1, 3];
9. [1, 19] + [8, 11].