Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т. е. до шифрования) тексте и буквами алфавита в закрытом (т. е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.

Однако, память у членов жюри оказалась уже не та, что в молодые годы, поэтому часто они путали, какие буквы надо было заменять на какие. В результате теперь они не могут восстановить свои материалы, а олимпиада уже на носу!

Чтобы разрешить свои проблемы, они обратились к вам. Для облегчения вашей задачи они выписали на бумажку все возможные варианты зашифрования букв, которые они могли применять, в виде набора пар "открытая буква" и "зашифрованная буква". Также вам известны все пары букв N-ского алфавита, которые могут следовать одна за другой в открытом тексте. Ваша задача состоит в том, чтобы по заданному зашифрованному слову сказать, соответствует ли ему хоть одно расшифрованное слово, единственен ли вариант расшифровки, и привести пример вариантов расшифровки слова. Слово A считается возможной расшифровкой слова B, если, во-первых, его можно "зашифровать" (заменяя каждую букву на одну из соответствующих ей "зашифрованных" букв), получив слово B, и, во-вторых, каждая пара букв слова A, стоящих рядом, является допустимой для N-ского языка.

Задана последовательность из n чисел a₁, a₂, ..., a_n. Подпоследовательностью длины k этой последовательности называется набор индексов i₁, i₂, ..., i_k, удовлетворяющий неравенствам 1 ≤ i₁ < i₂ < ... < i_k ≤ n. Подпоследовательность называется возрастающей, если выполняются неравенства a_i1 < a_i2 < ... < a_ik.

Необходимо найти число возрастающих подпоследовательностей наибольшей длины заданной последовательности a₁, ... ,a_n. Так как это число может быть достаточно большим, необходимо найти остаток от его деления на 10⁹ + 7.

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

Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки 10·1·50 + 50·20·5 + 10·50·5 = 500 + 5000 + 2500 = 8000. Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким: 1·50·20 + 1·20·5 + 10·1·5 = 1000 + 100 + 50 = 1150.

(Задача отличается от предыдущых исключительно ограничениями.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f ₁ , f ₂ , ..., f _N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K ₁ -ый должны соответствовать 1-ой клавише, с ( K ₁ + 1) -ого по некоторый K ₂ -ой — 2-ой клавише и т. д., до K _M = N . Конкретные значения K ₁ , K ₂ , ..., K _{M - 1} не задаются — их, наоборот, нужно подобрать.

Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.

(Задача отличается от предыдущых исключительно ограничениями.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N -й символы алфавита использованы в сообщении f ₁ , f ₂ , ..., f _N раз. Его необходимо набрать на M -клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K ₁ -ый должны соответствовать 1-ой клавише, с ( K ₁ + 1) -ого по некоторый K ₂ -ой — 2-ой клавише и т. д., до K _M = N . Конкретные значения K ₁ , K ₂ , ..., K _{M - 1} не задаются — их, наоборот, нужно подобрать.

Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.