Problem 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ă).

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

General info

ID: 96

Upload: liviu

Input: Console Input

Memory limit: 128MB/128MB

Time limit: 0.65s

Source: Sursă: Lot 2021 Baraj 2 Seniori: Problema 3

Submissions

Special Submissions