С древних времён ужасный крылатый Сфинкс подстерегает путников у Большого Камня по дороге в священный город Истины, задаёт им хитроумные загадки и съедает тех, кто не сумел дать правильный ответ. Турист Пётр тоже решил посетить город Истины и встретил чудовище.

Сфинкс задал ему такую загадку: «На Большом Камне написано число n . Найди наименьшее целое положительное число k , такое что сумма цифр числа k в десятичной системе счисления делится на n и сумма цифр числа k + 1 в десятичной системе счисления делится на n ».

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

Когда-то давно во Франции жил граф по имени Бутер де Бит. С момента, как он научился писать и рисовать, он прожил n лет и n - 1 зим. И с того самого момента он вёл дневник на длинной полоске пергамента, в котором описывал лета и зимы, свидетелем которых он был.

Каждое лето он записывал цифру от 0 до 9 , характеризующую, насколько солнечным было это лето. Зимы же граф Бутер описывал проще: если снега зимой было много, значит зима удалась, если снега было мало, значит зима вышла неудачной. Каждую удачную зиму он рисовал в своём дневнике снежинку после последней записанной цифры, а каждую неудачную он не рисовал ничего. Снежинка при этом выглядела следующим образом: * .

Много лет спустя некто Артур Бабаев нашел эту полоску пергамента. На нём были написаны n цифр, и между некоторыми из них были нарисованы снежинки, которые он воспринял как знак умножения. Он быстро посчитал получившееся число, но это было слишком просто для него.

Артур принадлежит к обществу Любителей Квантовой Механики и знает, что наша вселенная не единственна. Более того, в каждой параллельной вселенной жило по такому же графу Бутер де Биту, и единственное, в чём отличалось существование разных де Битов, это удачность зим, которые они переживали. А именно, каждая из 2 ^{n - 1} последовательностей удачных/неудачных зим встречалась ровно в одной вселенной. Аналогичным образом в каждой вселенной существовало по Артуру, нашедшему этот самый лист пергамента и посчитавшему значение выражения на нём.

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

Заметим, что ни одного из Артуров не смутит ситуация, в которой один из образовавшихся на полоске сомножителей содержит ведущие нули. Например, полоска пергамента, на которой написана строка 01 * 02 , задаёт корректное выражение, значение которого равняется 2 .

Осенью в одной провинциальной средневековой общине на юго-востоке Уэльса проходит делёж собранного урожая яблок. Эта община имеет внутреннюю иерархию, согласно которой каждый из n человек имеет ранг, являющийся целым положительным числом от 1 до n , причём все люди имеют разные ранги.

Процесс дележа урожая проходит следующим образом:

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

Вам стало интересно, насколько данная процедура дележа яблок является честной. Определите, какое минимальное количество яблок может оказаться у человека после участия в описанной процедуре.

Гриша, подобно персонажу известной кинокомедии, нашел себе ночную работу в музее естественной истории. В первую же смену ему выдали его главное орудие труда — эмбоссер — и приказали провести инвентаризацию всей экспозиции.

Эмбоссер представляет собой устройство для «печати» текста на пластиковой ленте. Текст набирается последовательно, буква за буквой. В устройство входят колесо с нанесёнными по кругу строчными буквами английского алфавита, неподвижная засечка, которая указывает на текущую букву, и кнопка, печатающая выбранную букву. За одно действие можно повернуть колесо с алфавитом на одну букву влево либо вправо по циклу. Изначально засечка эмбоссера указывает на букву a. Остальные буквы расположены так, как показано на рисунке.

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

Молодой известный дизайнер Пётр решил устроить мастер-класс для широких масс. Он планирует, что на мастер-классе каждый участник создаст свой неповторимый шедевр. Пётр собирается подготовить для каждого участника огромный белый холст \(h \ см \times w \ см\) (\(h\) и \(m\) — целые числа) и баночку краски чёрного цвета, которой хватает ровно на \(s \ см^2\) холста.

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