GREAT + SWERC = PORTO

We want to have a great SWERC at Porto this year, and we approached this challenge in several ways. We even framed it as a word addition problem, similar to the classic SEND + MORE = MONEY, where each letter stands for a single digit (0, 1, 2, …, 8, 9) that makes the arithmetic operation correct. In word additions, different letters cannot be assigned the same digit, and the leftmost letter in a word cannot be zero (0). In particular, a single-letter term cannot be zero.

To solve this word addition problem, we had to find positive digits for G, S, and P, and digits for R, E, A, T, W, C, O, so that each letter has a different digit and the sum is correct. It turns out that, unlike the classical SEND + MORE = MONEY, which has a single solution, GREAT + SWERC = PORTO has six solutions:

T = 7, E = 3, W = 9, G = 1, A = 0, P = 4, S = 2, C = 8, R = 6, O = 5
T = 7, E = 3, W = 9, G = 2, A = 0, P = 4, S = 1, C = 8, R = 6, O = 5
T = 8, E = 5, W = 1, G = 3, A = 7, P = 9, S = 6, C = 4, R = 0, O = 2
T = 8, E = 5, W = 1, G = 6, A = 7, P = 9, S = 3, C = 4, R = 0, O = 2
T = 9, E = 5, W = 2, G = 1, A = 8, P = 7, S = 6, C = 4, R = 0, O = 3
T = 9, E = 5, W = 2, G = 6, A = 8, P = 7, S = 1, C = 4, R = 0, O = 3

Having more than one solution does not make GREAT + SWERC = PORTO a good problem to solve by hand, but it is still a piece of cake for a programmer. Moreover, it gives us another reason to organize SWERC again next year and, who knows, in years to come!

Given a word addition problem, compute the number of solutions (possibly zero).

Input Specification

The input contains several test cases, each of them as described below.

Each test case consists of a line with an integer n (3 ≤ n ≤ 10), followed by n lines, each containing a word with a maximum length of 10 letters. The first n – 1 words are the terms to be added, and the last line is the result. Words contain only capital letters. If words have different lengths, they must be interpreted as aligning to the right. For instance, in the SEND + MORE = MONEY problem, the D of the first word and the E of the second word align with the Y of the final word. You can also assume that the size of the last word is greater than or equal to the maximum size of the preceding words, and moreover, at most ten distinct letters are involved in a word problem.

Output Specification

For each test case, output a single line with an integer: the number of solutions of the word addition problem given as input.

Sample Input

1. 3
2. GREAT
3. SWERC
4. PORTO
5. 3
6. SEND
7. MORE
8. MONEY
9. 5
10. TOO
11. GOOD
12. TO
13. BE
14. TRUE

download as text file

Output for Sample Input

1. 6
2. 1
3. 93

download as text file

Original Problem

Southwestern Europe Regional Contest, 2014