Крош для входа в тестовую систему одного из сайтов по программированию придумал пароль. Но, вот незадача: вскоре Крошу захотелось порешать задачи и на другом сайте, а потом и на третьем. Так как Крошу лень придумывать кардинально новый пароль каждый раз, он решил в качестве нового пароля брать пароль, который является перестановкой символов пароля на самом первом сайте. А чтобы не ошибиться, он хочет, чтобы новый пароль отличался от первоначального не более чем в $$$3$$$ символах. То есть должно существовать не более трех индексов $$$1 \le i \le len(s)$$$, таких, что $$$s(i) \neq t(i)$$$, где $$$s$$$ – исходная строка, $$$t$$$ – новый пароль и $$$len(s)$$$ – их длина. Сгенерируйте для Кроша $$$x$$$ таких паролей. Гарантируется, что для входной строки это можно сделать. Гарантируется, что $$$x = 10$$$ для семпла и $$$x = 100$$$ – для всех остальных наборов входных данных.

Крош недавно ознакомился с битовыми операциями и ему в голову пришла следующая задача: Пусть дан массив $$$A$$$ из $$$2^n$$$ неотрицательных элементов $$$a_0, a_1, ..., a_{2^n - 1}$$$. Ему нравится операция побитового исключающего ИЛИ – xor, поэтому он рассматривает все пары индексов $$$(i, j)$$$, такие, что $$$i \oplus j = k$$$, где $$$k$$$ – заданное число, $$$\oplus$$$ – операция побитового исключающего ИЛИ. По всем таким парам он хочет найти наибольшее суммарное значение величины $$$a_i + a_j$$$.

• Подзадача 1 (40 баллов) $$$n \le 9$$$.
• Подзадача 2 (60 баллов) без дополнительных ограничений

У Кроша есть массив из $$$n$$$ элементов, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Каждый элемент имеет значение $$$a_i$$$ и стоимость удаления $$$c_i$$$. Крош играет на этом массиве в следующую игру. За один ход он берет пару соседних элементов и удаляет из них наименьший по значению, при этом платит стоимость удаления наименьшего по значению элемента за эту операцию. То есть, удаляем наименьший элемент и платим его стоимость удаления. У Кроша есть сумма $$$s$$$, которую можно потратить на удаление элементов. Помогите ему найти наибольшее значение, которое может принять минимум этого массива после нуля или более операций. Обратите внимание, в массиве должен остаться хотя бы один элемент, так как для него не существует пары. При удалении элементы смещаются, то есть не остаётся пропусков.

• Подзадача 1 (50 баллов) $$$n \le 100$$$
• Подзадача 2 (50 баллов) без дополнительных ограничений, необходимые подазадачи – 1

Перед вами есть числовая прямая, на которой выделено $$$n$$$ точек, пронумерованных слева направо от $$$1$$$ до $$$n$$$. Известно, что на эти точки могут выпадать осадки. А именно, в момент времени $$$t_j$$$(в начале секунды номер $$$t_j$$$) на точку с номером $$$x_j$$$ выпадает $$$c_j$$$ единиц дождя. Каждая точка характеризуется скоростью высыхания дождя на ней. Известно, что на точке номер $$$i$$$ осадки высыхают со скоростью $$$v_i$$$ единиц в секунду. Если в точке меньше $$$v_i$$$ единиц, то после высыхания на ней останется $$$0$$$ единиц дождя. Считайте, что осадки выпадают мгновенно в начале указанной секунды на указанное место, а высыхание происходит в конце каждой секунды в каждой точке. Вам дано $$$m$$$ запросов. В запросе $$$j$$$ на точку $$$x_j$$$ в момент времени $$$t_j$$$ выпадает $$$c_j$$$ осадков. Обозначим $$$f_{ij}$$$ – количество осадков в момент времени $$$j$$$ на участке номер $$$i$$$. Для каждого участка $$$i$$$ посчитайте $$$\sum_{j = 1}^{10^{100}} f_{ij}$$$. Выведите $$$n$$$ полученных чисел. Для более ясного понимания, вам нужно посчитать суммарное количество осадков в каждой точке по всем возможным моментам времени(к моменту времени $$$10^{100}$$$ все осадки точно высохнут). Считайте, что измерение количества осадков проводится сразу непосредственно после выпадения осадков, до того как осадки начали высыхать в эту секунду. Например, если в какую-то точку выпало $$$10$$$ единиц осадков, а скорость высыхания в этой точке равна $$$3$$$, и в этой точке потом больше не было осадков, то вам нужно прибавить $$$10 + 7 + 4 + 1 = 22$$$.

• Подзадача 1 (20 баллов) $$$1 \le n \le 10, 1 \le m \le 10, 1 \le t_j \le 10, 1 \le c_j \le 10$$$
• Подзадача 2 (20 баллов) все $$$v_i = 1$$$
• Подзадача 3 (20 баллов) $$$n = 1$$$
• Подзадача 4 (40 баллов) без дополнительных ограничений, необходимые подзадачи – 1, 2, 3

У Кроша есть бинарная строка $$$s$$$ длины $$$n$$$, состоящая из $$$n$$$ символов $$$0$$$ и $$$1$$$. За один ход Крош может взять два различных соседних символа $$$s_i$$$ и $$$s_{i + 1}$$$ и заменить один из них на другой. Цена такой замены равна $$$c_i$$$. Например, если $$$s_i = 0$$$, $$$s_{i + 1} = 1$$$, то вы можете за $$$c_i$$$ заменить либо $$$0$$$ на $$$1$$$, либо $$$1$$$ на $$$0$$$. Найдите минимальную суммарную стоимость замен, с помощью которых можно получить строку, состоящую из всех единиц.

• Подзадача 1 (15 баллов): для любого $$$1 \le n \le 10$$$;
• Подзадача 2 (15 баллов): для любого $$$1 \le i \le n - 1$$$ $$$s_i \neq s_{i + 1}$$$, необходимые подзадачи – нет.
• Подзадача 3 (15 баллов): для всех $$$1 \le i \le n$$$ $$$c_i = 1$$$
• Подзадача 4 (55 баллов): без дополнительных ограничений, необходимые подзадачи – 1, 2, 3.

У Кроша есть множество из $$$n$$$ натуральных чисел $$$1, 2, 3, ..., n$$$, а также число $$$p$$$. Он называет пару чисел $$$a, b$$$, где $$$1 \le a \lt b \le n$$$ интересной, если произведение этих чисел делится на $$$6$$$, а разность равна $$$p$$$. Посчитайте количество интересных пар для Кроша.

• Подзадача 1 (15 баллов) $$$n \le 500$$$
• Подзадача 2 (20 баллов) $$$n \le 10^5$$$, необходимые подзадачи – 1
• Подзадача 3 (20 баллов) $$$p$$$ делится на $$$6$$$
• Подзадача 4 (20 баллов) $$$p$$$ делится на $$$2$$$ или $$$3$$$, необходимые подзадачи – 3
• Подзадача 5 (25 баллов) без дополнительных ограничений, необходимые подзадачи – 1, 2, 3, 4

Рассмотрим следующую задачу. Вам дан набор из $$$n$$$ пар положительных элементов: $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, $$$(a_3, b_3)$$$, ..., $$$(a_n, b_n)$$$. Выберем из каждой пары одно число: $$$c_i = a_i$$$ или $$$c_i = b_i$$$ для каждого $$$1 \le i \le n$$$. Назовем задачу решаемой, если можно выбрать последовательность $$$c$$$ такую, что она будет строго возрастать, то есть $$$c_1 \lt c_2 \lt ... \lt c_n$$$. Для заданной последовательности пар посчитайте, сколько их перестановок из $$$n!$$$ будут приводить к решаемой задаче.

• Подзадача 1 (10 баллов): для любого $$$1 \le i \le n$$$ $$$a_i = b_i$$$;
• Подзадача 2 (15 баллов): для любого $$$1 \le i \le n$$$ $$$|a_i - b_i| \le 1$$$, необходимые подзадачи – 1.
• Подзадача 3 (25 баллов): $$$1 \le n \le 10$$$
• Подзадача 4 (30 баллов): $$$1 \le n \le 16$$$, необходимые подзадачи – 3
• Подзадача 5 (20 баллов): без дополнительных ограничений, необходимые подзадачи – 1, 2, 3, 4

У Кроша есть матрица из $$$n$$$ строк, пронумерованных от $$$0$$$ до $$$n - 1$$$, и $$$m$$$ столбцов, пронумерованных от $$$0$$$ до $$$m - 1$$$. Элемент в левой верхней ячейке равен $$$x$$$: $$$a_{00} = x$$$, где $$$x$$$ – заданное число. Остальные значения матрицы вычисляются следующим способом. Матрица заполняется сверху вниз, слева направо: сначала заполняется $$$0$$$-я строка, затем $$$1$$$-я и т. д. Строки заполняются слева направо. Значение в каждой ячейке вычисляется следующим образом: $$$a_{ij} = \oplus$$$ (всех уже заполненных к этому моменту значений матрицы) $$$\oplus i \oplus j$$$, где $$$\oplus$$$ – операция побитового исключающего ИЛИ – ксор. Вам нужно ответить на множество запросов. В каждом запросе вам даны числа $$$n, m, x, y$$$. Выведите в ответе на этот запрос $$$1$$$, если в матрице Кроша размера $$$n$$$ на $$$m$$$, левое верхнее значение которой равно $$$x$$$, есть элемент, равный $$$y$$$, и $$$0$$$ в противном случае.

• Подзадача 1 (20 баллов) $$$t \le 10, n \le 10, m \le 10$$$
• Подзадача 2 (25 баллов) ограничения на $$$t$$$ нет, $$$n \le 1000$$$, $$$m \le 1000$$$, дополнительно гарантируется, что все $$$m$$$ равны между собой и что все $$$x$$$ равны между собой
• Подзадача 3(10 баллов) ограничения на $$$t$$$ нет, $$$n \le 1000$$$, $$$m \le 1000$$$, дополнительно гарантируется, что все $$$m$$$ равны между собой($$$x$$$ могут отличаться), необходимые подзадачи – 2
• Подзадача 4 (45 баллов) без дополнительных ограничений, необходимые подзадачи – 1, 2, 3

У Кроша есть множество из $$$n$$$ натуральных чисел от $$$1$$$ до $$$n$$$. Он называет подмножество этого множества из $$$k$$$ элементов красивым, если наибольший общий делитель всех элементов подмножества равен $$$1$$$. Помогите ему посчитать количество красивых подмножеств из $$$k$$$ элементов. Так как ответ может быть большим, выведите его остаток от деления на $$$10^9+7$$$.

• Подзадача 1 (10 баллов) $$$k = 2, n \le 100$$$
• Подзадача 2 (14 баллов) $$$k = 2, n \le 10^5$$$, необходимые подзадачи – 1
• Подзадача 3 (14 баллов) $$$n \le 20$$$
• Подзадача 4 (18 баллов) $$$n \le 500$$$, необходимые подзадачи – 1, 3
• Подзадача 5 (18 баллов) $$$n \le 2000$$$, необходимые подзадачи – 1, 3, 4
• Подзадача 6 (26 баллов) без дополнительных ограничений, необходимые подзадачи – 1, 2, 3, 4, 5