artifact

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ță

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 artifact.out se va scrie pe prima linie numărul de soluții distincte ale ecuației date.

Restricții și precizări

• $1 \leq N$
• $1 \leq M$
• $N+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 $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 solutie: $5 + 5 + 5 = 15$

Exemplul 2

artifact.in

2 1
THIS IS EASY

artifact.out

7

Explicație

THIS + IS = EASY admite $7$ solutii:
$7962 + 62 = 8024$
$5974 + 74 = 6048$
$1974 + 74 = 2048$
$2974 + 74 = 3048$
$5987 + 87 = 6074$
$1987 + 87 = 2074$
$2987 + 87 = 3074$