Pracsiu Dan (dnprx) 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 + 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 A la Z. Se presupune că suma primelor N numere trebuie să fie egală cu suma ultimelor M numere. De asemenea, fiecare literă corespunde unei cifre de la 0 la 9, iar două litere diferite sunt asociate cu două cifre diferite.
Cerința
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 N și M separate printr-un spațiu. Pe a doua linie sunt scrise cele N + M șiruri de caractere, separate prin câte un spațiu, reprezentând termenii ecuației.
Date de ieșire
În fișierul de ieșire artifact.out se va scrie pe prima linie numărul de soluții distincte ale ecuației date.
Restricții și precizări
1 ≤ N,1 ≤ M,N + M ≤ 5000- Fiecare număr este codificat prin cel mult
14caractere - Numerele codificate cu cel puțin două cifre nu pot avea cea mai semnificativă cifră egală cu
0 - 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 soluție: 5 + 5 + 5 = 15
Exemplul 2:
artifact.in
2 1 THIS IS EASY
artifact.out
7
Explicație
THIS + IS = EASY admite 7 soluții:
7962 + 62 = 8024
5974 + 74 = 6048
1974 + 74 = 2048
2974 + 74 = 3048
5987 + 87 = 6074
1987 + 87 = 2074
2987 + 87 = 3074