eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

GREAT+SWERC=PORTO

GREAT+SWERC=PORTO

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Мы хотим провести знаменитый SWERC в Порту в этом году, поэтому подошли к решению этой проблемы несколькими способами. Мы сформулировали ее как проблему сложения слов, аналогично классической SEND + MORE = MONEY, где каждая буква обозначает одну цифру (0, 1, 2, ..., 8, 9), что делает арифметическую операцию корректной. При сложении слов разным буквам не может соответствовать одна и та ж цифра, а крайняя левая буква в слове не может быть нулевой (0). В частности, однобуквенный термин не может быть нулевым.

Для решения задачи сложения следует найти такие положительные цифры для G, S и P, и цифры для R, E, A, T, W, C, O, что каждая буква соответствует разной цифре и сумма будет корректной. В отличии от классического ребуса SEND + MORE = MONEY имеющего единственное решение, ребус GREAT + SWERC = PORTO имеет шесть решений.

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

Наличие более одного решения не делает ребус GREAT + SWERC = PORTO лучшей задачей, которую нужно решить вручную, но для программиста не все так просто. Более того, это дает нам еще одну причину организовать SWERC снова в следующем году и, возможно, в ближайшие годы!

Для заданной задачи сложения слов найдите количество ее решений (возможно, ноль).

Вхідні дані

Первая строка содержит целое число n (3n10). За ней следуют n строк, каждая из которых содержит слово из не более чем 10 букв. Первые n - 1 слов являются слагаемыми, а последнее - суммой.

Слова содержат только заглавные буквы. Если слова имеют разные длины, их следует выравнить вправо. Например, в задаче SEND + MORE = MONEY, букву D из первого слова и букву E со второго слова следует выравнить с буквой Y результирующего слова. Считайте, что размер последнего слова больше или равен максимальному размеру предыдущих слов, и, кроме того, не более десяти отдельных букв вовлечены в задачу со словами.

Каждое слово содержит не более 10 символов (заглавных букв). Задача сложения содержит не более 10 различных букв.

Вихідні дані

Вывести количество решений входного ребуса.

Приклад

Вхідні дані #1
3
GREAT
SWERC
PORTO
Вихідні дані #1
6
Вхідні дані #2
3
SEND
MORE
MONEY
Вихідні дані #2
1
Джерело 2014 ACM Southwestern Europe Regional Contest (SWERC), Задача A