Задача 91. Позвони мне ≡

Условие

Позвони мне, позвони,

Позвони мне, ради Бога.

Через время протяни

Голос тихий и глубокий.

...

Роберт Рождественский, "Позвони мне, позвони", 1980 г.

Видеоклип

В наши дни звонков ждут не только обычные люди. Многие коммерческие организации тоже рады обращениям новых и старых клиентов, они делают всё возможное, чтобы упростить такого рода коммуникацию и, в частности, облегчить запоминание своих телефонных номеров.

Слово-номер — это мнемоническая фраза, представляющая собой цифро-буквенный эквивалент телефонного (или другого) номера. Во многих странах на кнопках телефона кроме цифр указаны ещё и символы. Буквы, соответствующие данному номеру, могут составлять слова, части слов, акронимы или аббревиатуры. Слово-номер легче запомнить, чем обычный цифровой номер, поэтому бизнес использует их как инструмент для прямого отклика на рекламу по радио, телевидению, в печати, на вывесках и т. п., сообщает Википедия.

На рисунке выше вы можете видеть соответствие латинских букв и цифр телефонного номера. Например, слово-номер HELLOWORLD однозначно соответствует номеру (или части номера) телефона 4355696753. Обратите внимание, что цифры 0 и 1 не используются — им не соответствуют никакие буквы.

Биг-Биг Банк, в котором молодой программист Роберт проходит стажировку, выкупил у телефонного оператора права на использование десяти миллионов номеров (от 0000000 до 9999999). В отделе рекламы долго шло согласование наиболее подходящих терминов для слов-номеров. В результате были приняты следующие правила:

• слово-номер должно состоять из 7 латинских букв, чтобы полностью заменять число номера, при этом будут использованы только слова из утверждённого списка длиной от 2 до 5;
• слова из списка нужно объединять: к любому слову из двух букв можно приписать справа любое слово из пяти букв (но не наоборот!), аналогично к любому слову из трёх букв можно приписать справа любое слово из четырёх букв (наоборот, опять же, нельзя).

Помогите Роберту определить количество различных номеров, соответствующих всех подходящим под вышеприведённые правила требованиям.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество утверждённых слов. В следующих n строках приведены сами слова длиной от 2 до 5, состоящие из заглавных латинских букв.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 1000, получат не менее 60 баллов.

Пояснение к примеру

В примере дано семь слов. Из них можно получить следующие слово-номера и номера телефонов:

• MYMONEY (телефонный номер 6966639);
• MYDEBIT (телефонный номер 6933248);
• BIGBANK (телефонный номер 2442265);
• BIGCASH (телефонный номер 2442274);
• NEWBANK (телефонный номер 6392265);
• NEWCASH (телефонный номер 6392274).

Всего шесть уникальных номеров телефонов.

Примеры тестов

7
MY
BIG
BANK
MONEY
NEW
CASH
DEBIT

6