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 різних літер.
Вихідні дані
Виведіть кількість рішень вхідного ребуса.