Был обычный весенний вечер. За окном завывала метель. Бухгалтер Евгений скучал на работе и с грустью вспоминал о своих былых успехах на олимпиадах по программированию. В его школьные годы на олимпиадах давали не больше восьми задач, и, разглядывая график своих успехов на сайте Topforces, ему удалось подсчитать, что в \(v_1\) олимпиадах он решил ровно 1 задачу, в \(v_2\) олимпиадах — ровно 2, \(\ldots\), в \(v_8\) олимпиадах — ровно 8 задач (Евгений предпочитал не вспоминать об олимпиадах, на которых он ничего не решил). К концу рабочего дня в офисе не осталось чистой бумаги, а из всех электронных устройств включенным оставался только калькулятор. Нашему герою ничего другого не оставалось, кроме как ввести памятные ему числа в калькулятор: \(v_1 1 v_2 2 \ldots v_8 8\). Стоит заметить, что никаких пробелов и других разделителей на калькуляторе Евгения не было, поэтому он записал эти числа просто подряд, получив некоторое число \(N\). Кроме того, он был достаточно ленив, поэтому все \(v_i\) вводил без ведущих нулей, а если какое-то \(v_i\) равнялось нулю, то соответствующую пару \(v_i i\) он просто не вводил.

Например, если \(v_2 = 111\), \(v_3 = 1\), а все остальные \(v_i = 0\), то у Евгения получилось бы число \(N = 111213\).

Уйдя с работы, Евгений оставил калькулятор с введенным числом \(N\) на столе, чем и воспользовалась его любопытная коллега Марина. Она сразу догадалась, как образовано введенное число, и уже собиралась приступать к расшифровке, как вдруг поняла, что различных наборов \((v_1, \ldots, v_8)\), из которых можно было получить это число, может быть достаточно много. Так, приведенное выше число \(N\) может быть получено также и при \(v_1 = 11\), \(v_3 = 21\).

Марина попросила вас найти количество таких наборов по модулю числа \(1\,000\,000\,007 = 10^9 + 7\).

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

Игровое поле представляет собой бесконечную горизонтальную ленту, разбитую на ячейки, пронумерованные целыми числами слева направо (см. рис.). Изначально в ячейках с отрицательными номерами расположена армия монстров, у каждого из которых есть некоторое количество единиц здоровья. А именно, в ячейках \(-1, -2, \ldots, -K\) расположены монстры с 1 единицей здоровья, в следующих \(K\) ячейках (с номерами \(-(K+1), \ldots, -2K\)) расположены монстры с 2 единицами здоровья и так далее. Таким образом, для каждого целого положительного числа \(i\) в ячейке с номером \(-i\) изначально находится монстр с \(\left\lceil\frac{i}{K}\right\rceil\) единицами здоровья. Кроме того, на ленте расположены две башни, каждая из которых контролирует некоторый отрезок ленты: первой башне соответствуют все ячейки с \(A\) по \(B\) включительно, а второй - ячейки с \(C\) по \(D\) включительно (\(0 \leqslant A \leqslant B \lt C \leqslant D\)).

Например, при \(K = 3\), \(A = B = 1\), \(C = 3\), \(D = 4\) исходная позиция будет выглядеть следующим образом:

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

Игра заканчивается, как только впервые в ячейке с номером \(D + 1\) окажется монстр.

Как вы уже могли заметить, главная проблема игры заключается в том, что для выигрыша может потребоваться слишком много нажатий на кнопку, поэтому для некоторых особо сложных уровней решено ограничить возраст игроков, допускаемых к его прохождению. В связи с этим вам нужно определить, сколько нажатий на кнопку потребуется для победы на данном уровне, который описывается числами \(K\),\(A\), \(B\), \(C\) и \(D\).

Каждое утро капитан Ъ проводит занятия по строевой подготовке в возглавляемой им роте солдат. Всего в роте N солдат, каждый из которых носит форму определенного цвета. Различных цветов формы не более 26, так что для удобства солдаты обозначают цвета строчными латинскими буквами. Таким образом, каждому из \(N\) солдат соответствует буква от 'a' до 'z' — цвет его формы.

За многие месяцы службы солдаты выяснили, что капитан пребывает в наилучшем расположении духа в том случае, когда цвета формы солдат в шеренге образуют определенную последовательность. Недолго думая, они выписали соответствующую строку \(S\) из \(N\) букв на асфальте и договорились, что отныне каждый должен при построении вставать именно на ту букву, которая соответствует цвету его формы.

Но к 23 февраля солдаты решили удивить капитана и поменяться местами так, чтобы \(каждый\) солдат встал не на ту букву, которая соответствует цвету его формы. Так, солдат с цветом формы 'q' может встать на любую букву, кроме буквы 'q', иначе удивление капитана будет недостаточным.

Помогите солдатам организовать праздничное построение: по данной строке \(S\), обозначающей старую последовательность цветов, выведите строку \(T\), являющуюся перестановкой символов строки \(S\) и обозначающую новую последовательность цветов. i-й символ строки T должен отличаться от i-го символа строки \(S\).