GREAT+SWERC=PORTO
Мы хотим провести знаменитый 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 (3 ≤ n ≤ 10). За ней следуют n строк, каждая из которых содержит слово из не более чем 10 букв. Первые n - 1 слов являются слагаемыми, а последнее - суммой.
Слова содержат только заглавные буквы. Если слова имеют разные длины, их следует выравнить вправо. Например, в задаче SEND + MORE = MONEY, букву D из первого слова и букву E со второго слова следует выравнить с буквой Y результирующего слова. Считайте, что размер последнего слова больше или равен максимальному размеру предыдущих слов, и, кроме того, не более десяти отдельных букв вовлечены в задачу со словами.
Каждое слово содержит не более 10 символов (заглавных букв). Задача сложения содержит не более 10 различных букв.
Выходные данные
Вывести количество решений входного ребуса.