Как-то раз, разбирая вещи на чердаке, Петя нашел странную игру. В начале игры на поле выкладываются карточки с числами. Затем двое игроков по очереди берут себе по одной карте за ход. Игра заканчивается, когда на поле не остается карточек. Выигрывает тот, у кого сумма чисел на карточках делится на три. В случае если сумма чисел делится на три у обоих игроков, объявляется ничья. Также ничья объявляется, если ни у одного игрока сумма не делится на три.

Петя выяснил, что эта игра была довольно популярна когда-то, и что у некоторых его друзей она тоже есть. Единственное отличие состоит в том, что набор карт у всех разный.

Теперь Пете интересно, каков будет исход партии при оптимальной игре. Помогите ему выяснить это.

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

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

Вам необходимо написать программу, которая будет считать количество способов раздать таким образом k наград среди n стоящих в ряд работников. Так как это число может быть весьма большим, необходимо найти его остаток от деления на простое число m .

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

К счастью, скоро настало время выпускных экзаменов, игра была позабыта, а вскоре потерялась при обновлении системы. Освободившееся время Витя потратил с пользой: сдал экзамены на «хорошо» и «отлично», поступил в университет, а через шесть лет, успешно защитив магистерскую диссертацию, устроился на работу ведущим программистом.

Беда пришла, откуда не ждали. Недавно вышла новая версия игры, Zuma 2.0 . В этой версии сюжет игры сделался более разнообразным, в частности, на разных уровнях игры действуют разные правила. Игра снова захватила Витю... простите, теперь уже Виктора Сергеевича. Однако, Виктор Сергеевич осознает, что игру нужно пройти как можно быстрее, чтобы вернуться к своим должностным обязанностям. В частности, ему никак не дается предпоследний уровень, поэтому он просит Вас помочь ему сделать это.

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

• Уничтожить любые два шара, на которых написаны одинаковые буквы.
• Уничтожить любые три шара, на которых написаны гласные буквы, а именно, «A», «E», «I», «O», «U», «Y» (см. примечание).

После выстрела оставшиеся шары смыкаются, вновь образуя окружность.

Если на уровне осталось менее пяти шаров, то игрок получает очки — чем меньше шаров осталось, тем больше очков он получает. Если же осталось пять или более шаров, а выстрел сделать не получается, то уровень считается непройденным.

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

Умный мальчик Вася — начинающий математик. Сегодня у него день рождения: собралось много гостей, все дарят ему подарки — все как обычно. Но его лучший друг Вовочка сделал ему необычный подарок: он подарил ему устройство, на котором был цифровой дисплей. Он отображает N -значное число X , с помощью N индикаторов из семи полосок.

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

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

Так как Вася не так хорош в математике как Вовочка, он просит вас написать программу, которая даст ответ на его вопрос.