Мальчик Ярослав захотел на обед съесть $$$n$$$ вопперов. Сначала он ест первый воппер, затем второй, третий и так далее. Вкусность $$$i$$$-го воппера равна $$$a_i$$$.

Так как у Ярослава СДВГ, ему тяжело есть воппер, когда его вкусность не совпадает со вкусностью предыдущего съеденного воппера, поэтому сделать так он может ровно $$$m$$$ раз. Ему стало интересно, сколько существует различных последовательностей вопперов, которые он может съесть, если вкусность каждого воппера может быть любым целым числом от $$$1$$$ до $$$k$$$.

Более формально, требуется посчитать количество последовательностей $$$a$$$ длины $$$n$$$, состоящих из чисел от $$$1$$$ до $$$k$$$, таких что существует ровно $$$m$$$ индексов $$$i$$$ ($$$2 \le i \le n$$$), для которых $$$a_i \ne a_{i-1}$$$.

Так как таких последовательностей может быть очень много, выведите ответ по модулю $$$10^9 + 7$$$.

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

Работа на кухне ресторана «Бургер Кинг» — настоящее искусство, особенно когда дело касается сборки легендарного Воппера!

Перед вами находится прямоугольный органайзер с ингредиентами, представляющий собой матрицу размера $$$n \times m$$$. Органайзер заполнен настолько разнообразными компонентами (от хрустящего маринованного огурчика до фирменного соуса), что каждый из них уникален. Каждой ячейке присвоен уровень важности от $$$0$$$ до $$$n \cdot m - 1$$$, причём все уровни встречаются ровно по одному разу. Уровень важности ингредиента, расположенного в $$$i$$$-й строке и $$$j$$$-м столбце, равен $$$a_{i, j}$$$.

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

Вкус идеального Воппера определяется тем, насколько последовательно собраны базовые ингредиенты. Формально, вкус бургера равен $$$\operatorname{MEX}$$$ множества уровней важности ингредиентов в зачерпнутой подматрице.

Напомним, что $$$\operatorname{MEX}$$$ (Minimum Excluded) множества чисел — это минимальное неотрицательное целое число, которое не принадлежит этому множеству. Например, $$$\operatorname{MEX}$$$ множества $$$\{0, 1, 3, 4\}$$$ равен $$$2$$$, а $$$\operatorname{MEX}$$$ множества $$$\{1, 2\}$$$ равен $$$0$$$.

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

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

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

Что может быть лучше воппера? Только двойной воппер! А что насчёт $$$k$$$-ного воппера? Боб захотел нажраться как свинья, но Алиса хочет ему помешать!

В «Бургер Кинге» провели реформу, и теперь там есть $$$n$$$ касс, пронумерованных от $$$0$$$ до $$$n - 1$$$. Для каждой кассы заданы два числа: $$$a_i$$$ и $$$k_i$$$ — соответственно изменение количества котлет в воппере при посещении этой кассы и её важность. Значение $$$a_i$$$ может быть отрицательным, тогда количество котлет уменьшается.

Все посетители начинают путь с кассы $$$n - 1$$$ и затем переходят между кассами, пока не дойдут до кассы $$$0$$$. Находясь в кассе с номером $$$i$$$ ($$$0 \lt i \lt n$$$), можно перейти либо в кассу с номером $$$i - 1$$$, либо выбрать число $$$b$$$ ($$$1 \lt b \le k_i$$$) и перейти в кассу с номером $$$\lfloor i / b \rfloor$$$.

До посещения кассы $$$n-1$$$ в воппере Боба содержится $$$10^{100}$$$ котлет (вы думали, мы блефовали в первом абзаце?). При посещении кассы с номером $$$i$$$ к вопперу обязательно добавляется $$$a_i$$$ котлет, не взять котлеты нельзя. Алиса и Боб ходят по очереди, причём Алиса ходит первой. Алиса стремится минимизировать итоговое количество котлет, а Боб — максимизировать его. Во время своего Алиса или Боб выбирают следующую кассу, в которую они перейдут.

Определите, сколько котлет будет в воппере при оптимальной игре обоих игроков.

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

Во времена Великого Ангуса, когда в королевстве «Бургер Кинг» ещё только складывались древние рецепты, каждый элемент массива считался отдельным ингредиентом для священного бургера. Число $$$a_i$$$ означало, какой именно ингредиент лежит на $$$i$$$-й полке королевской кладовой, всего полок было $$$n$$$.

Но в день Великого Ангусения жрецам было поручено необычное дело. Из отрезка кладовой с $$$l$$$-й по $$$r$$$-ю полку нужно было собрать ровно $$$k$$$ корзин ингредиентов, причём:

• ингредиент с $$$i$$$-й полки должен оказаться не более чем в одной корзине;
• в каждой корзине $$$\operatorname{MEX}$$$ набора ингредиентов должен быть равен $$$x$$$.

Здесь $$$\operatorname{MEX}$$$ — это наименьшее неотрицательное число, которого нет в выбранной корзине: именно оно считалось номером недостающего ингредиента в великом рецепте Ангуса.

Жрецы «Бургер Кинга» верили: если на отрезке кладовой посчитать количество способов собрать таким образом корзины, то в этот день Ангус будет особенно сочным, а королевство — сытым и довольным.

Так и поступают мудрецы: для каждого запроса с границами отрезка $$$[l, r]$$$ и числом $$$x$$$ они считают, сколькими способами можно выбрать множество из $$$k$$$ попарно непересекающихся подпоследовательностей $$$a_l, a_{l+1}, \ldots, a_r$$$ так, чтобы каждая подпоследовательность имела $$$\operatorname{MEX}$$$ равный $$$x$$$.

Обратите внимание, что две подпоследовательности считаются различными, если они состоят из элементов с различными индексами в массиве $$$a$$$. Например, в массиве $$$a = [0, 0, 0]$$$ на отрезке $$$[1,3]$$$ существует $$$7$$$ непустых подпоследовательностей с $$$\operatorname{MEX}$$$ равным $$$1$$$.

Вам предстоит выступить в роли мудреца и посчитать количество таких способов. Так как их может быть очень много, достаточно вывести ответы по модулю $$$10^9 + 7$$$.

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