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

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

Вам дана структура министерства. Каждый работник имеет одного начальника и не более трёх подчинённых(возможно ноль). Единственным исключением является министр  — у него нет начальника(но так же не более трех подчинённых). Конечно нет определённого порядка, в котором перечисляются подчинённые. Департамент состоит из должностного лица, всех его подчинённых и их подчинённых, и т.д.

Есть два особых случая:

• Департамент, в котором должностное лицо  — сам министр, тогда этот департамент есть всё министерство.

• Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i + 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

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

У одного медведя есть N строк (обозначим i -ю из них x _i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x _i и x _j ( i < j ) могут принадлежать одной такой последовательности, если x _i является и префиксом, и суффиксом x _j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.

У маленького Матежа возникла проблема с решением следующей задачи.

У него есть множество слов, содержащее N слов. Ему пришло Q запросов, являющихся шаблонами. Шаблон состоит из строчных латинских букв и символа '*'.

Требуется узнать, сколько слов из множества могут совпасть с шаблоном, если вместо '*' подставить любое (возможно, пустое) множество букв.

Вам дан массив целых чисел длины N . Пусть s ₁ , s ₂ , ... , s _q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 ^N - 1 .

Массив A лексикографически меньше массива B , если A _i < B _i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v ₁ , v ₂ , ... , v _p , как: h ( s )  =  ( v ₁ · B ^{p - 1} + v ₂ · B ^{p - 2} + ... + v _{p - 1} · B + v _p ) mod M , где B и M - данные числа.

Посчитайте h ( s ₁ ) , h ( s ₂ ) , ... , h ( s _K ) для данного K .

Палиндром - это слово, которое читается справа налево также, как слева направо. Например, "a", "abba", "anavolimilovana" - палиндромы.

Весом строки, состоящей из строчных латинских символов будем называть количество ее подстрок (слов), являющихся палиндромами (при этом каждое вхождение подстроки считается отдельно). Формально, пусть W - строка длины N . Слово w _{a , b} - подстрока W , состоящая из символов на позициях с индексами с a по b включительно. Вес строки W - это количество пар целых чисел a , b ( 1 ≤ a , b ≤ N ) таких, что w _{a , b} является палиндромом.

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