Digits

Time limit: 0.65s
Memory limit: 128MB
Input:
Output:

Î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 ai+bj=ka_i + b_j = k, aibj=ka_i − b_j = k, unde k este o constantă (posibil diferită pentru fiecare proprietate), iar a0,..,aN1a_0, .. , a_{N−1} și b0,...,bN1b_0, ... , b_{N−1} sunt cifrele celor două valori, unde a0a_0 și b0b_0 sunt cele mai nesemnificative, iar aN1a_{N−1} si bN1b_{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 109+710^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 ai+bj=ka_i + b_j = k, fie de forma i − j k reprezentând aibj=ka_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 109+710^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)

  • 1N18,ci=B11 ≤ 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 aia_i și bib_i.

Subtask 5 (18 puncte)

  • 1 ≤ N ≤ 18, B ≤ 30
  • Toate restricțiile sunt de forma ai+bj=ka_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 ak,...,a0a_k, ... , a_0, unde aka_k este cea mai semnificativă, și a0a_0 cea mai nesimnificativă, se notează cu [ak,...,a0][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].

Problem info

ID: 96

Editor: liviu

Author:

Source: Lot 2021 Baraj 2 Seniori: Problema 3

Tags:

Lot 2021 Baraj 2 Seniori

Log in or sign up to be able to send submissions!