artifact

Time limit: 0.25s Memory limit: 128MB Input: artifact.in Output: artifact.out

Arheologii au găsit un artifact care pare să conțină o ecuație matematică, care folosește simbolurile unei scrieri necunoscute încă. O serie de ipoteze au început să apară, așa că ei își propun să rezolve ecuația în vederea descifrării simbolurilor. Ecuația conține N+MN + M termeni, fiecare termen reprezentând un număr codificat printr-o înșiruire de simboluri, care au fost înlocuite cu literele mari ale alfabetului englez, de la AA la ZZ. Se presupune că suma primelor NN numere trebuie să fie egală cu suma ultimelor MM numere. De asemenea, fiecare literă corespunde unei cifre de la 00 la 99, iar două litere diferite sunt asociate cu două cifre diferite.

Cerință

Se cere să se afle câte soluții distincte admite ecuația găsită.

Date de intrare

În fișierul artifact.in pe prima linie se află două numere naturale nenule NN și MM separate printr-un spațiu. Pe a doua linie sunt scrise cele N+MN + M șiruri de caractere, separate prin câte un spațiu, reprezentând termenii ecuației.

Date de ieșire

În fișierul artifact.out se va scrie pe prima linie numărul de soluții distincte ale ecuației date.

Restricții și precizări

  • 1N1 \leq N
  • 1M1 \leq M
  • N+M5 000N+M \leq 5 \ 000;
  • Fiecare număr este codificat prin cel mult 14 caractere
  • Numerele codificate cu cel puțin două cifre nu pot avea cea mai semnificativă cifră egală cu 00;
  • Se garantează că ecuația are cel puțin o soluție;
  • Două soluții sunt distincte dacă cel puțin una din litere are valori diferite în cele două soluții;

Exemplul 1

artifact.in

3 1
A A A BA

artifact.out

1

Explicație

A + A + A = BA admite o singura solutie: 5+5+5=155 + 5 + 5 = 15

Exemplul 2

artifact.in

2 1
THIS IS EASY

artifact.out

7

Explicație

THIS + IS = EASY admite 77 solutii:
7962+62=80247962 + 62 = 8024
5974+74=60485974 + 74 = 6048
1974+74=20481974 + 74 = 2048
2974+74=30482974 + 74 = 3048
5987+87=60745987 + 87 = 6074
1987+87=20741987 + 87 = 2074
2987+87=30742987 + 87 = 3074

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