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

Например, если нам дан массив \([10, 20, 30, 40]\), мы можем переставить числа так, что массив станет \([20, 40, 10, 30]\). При этом на первой и второй позициях числа стали больше (\(20>10\), \(40>20\)), а на третьей и четвёртой — нет, значит для такой перестановки число, которое хочет максимизировать Вася, равно \(2\). Ознакомьтесь с примечанием к первому тестовому примеру, там разобран ещё один показательный тест.

Помогите Васе так переставить числа, чтобы количество позиций, в которых в новом массиве числа больше, чем в изначальном, было максимальным.

Леха собрался в путь из Москвы в Саратов. Он не любит ездить на поездах, поэтому решил отправиться из одного города в другой на машине.

Путь из Москвы в Саратов может быть представлен, как прямая (пожалуй, она не столь ровная в действительности, но в данной задаче будем считать так), и расстояние между Москвой и Саратовом равно \(n\) км. Считаем, что Москва расположена в точке с координатой \(0\) км, а Саратов — в точке с координатой \(n\) км.

Вести машину столь долгое время достаточно утомительно. Формально, если Леха преодолел \(i\) километров после того, как останавливался на отдых в прошлый раз, то сложностью преодоления \((i + 1)\)-го километра он считает величину \(a_{i + 1}\). Гарантируется, что для каждого \(i \in [1, n - 1]\) \(a_i \le a_{i + 1}\). Сложность пути определяется, как сумма сложностей по каждому километру пути.

К счастью, между Москвой и Саратовом могут быть места для отдыха. Каждая целочисленная точка от \(1\) до \(n - 1\) может содержать место для отдыха. Когда Леха заезжает на место для отдыха, он (разумеется) отдыхает, и следующий километр для него становится сложности \(a_1\), километр после этого — сложности \(a_2\) и так далее.

Например, если \(n = 5\) и есть место для отдыха в точке с координатой \(2\), то сложность пути получится \(2a_1 + 2a_2 + a_3\): первый километр будет иметь сложность \(a_1\), второй — \(a_2\), потом Леха отдохнет, и третий километр будет иметь сложность \(a_1\), четвертый — \(a_2\) и последний — \(a_3\). Другой пример: если \(n = 7\) и есть места для отдыха в точках с координатами \(1\) и \(5\), то сложность пути Лехи будет равна \(3a_1 + 2a_2 + a_3 + a_4\).

Леха не знает, какие из целочисленных точек содержат места для отдыха. Поэтому он хочет предусмотреть любую возможную ситуацию. Очевидно, есть \(2^{n - 1}\) вариантов различных распределений точек отдыха (два распределения различны, когда существует такая точка \(x\), что место для отдыха есть ровно в одном из данных распределений). Леха считает все распределения равновероятными. Он хочет посчитать \(p\) — математическое ожидание сложности пути.

Очевидно, \(p \cdot 2^{n - 1}\) — это целое число. Посчитайте его по модулю \(998244353\).

Рассмотрим упрощенную версию книги заявок некоторой акции.

Книга заявок — это список заявок (предложений) от людей, которые хотят купить или продать одну акцию, каждая заявка описывается направлением (BUY или SELL) и ценой.

В каждый момент времени у любой SELL заявки цена больше, чем у любой BUY заявки.

В этой задаче цены всех когда-либо существовавших заявок различны.

Заявка с направлением SELL с наименьшей ценой и заявка с направлением BUY с наибольшей ценой называются лучшими предложениями и выделены черной рамкой на рисунке.

Данная книга заявок говорит, что кто-то хочет продать акцию по цене \(12\), и это лучшее предложение с направлением SELL, потому что у других двух заявок с этим направлением цена выше. У лучшего BUY предложения цена \(10\).

В книге заявок возможны два события:

1. Кто-то добавил новую заявку с некоторым направлением и некоторой ценой
2. Кто-то принял лучшее SELL или BUY предложение (совершил сделку). Нельзя принять не лучшее предложение (совершать сделку по менее выгодной цене). После того, как лучшее предложение принято, оно навсегда удаляется из книги заявок.

Можно добавлять новые заявки BUY только с ценами ниже лучшего SELL предложения (если вы хотите купить по более высокой цене, то вместо постановки заявки нужно принять лучшее SELL предложение). Аналогично нельзя добавлять SELL заявки с ценами меньшими или равными лучшему предложению BUY. К примеру, нельзя добавить заявку "SELL \(20\)", если уже есть заявка "BUY \(20\)" или "BUY \(25\)" — в этом случае нужно просто принять лучшее предложение BUY.

У вас есть поврежденный лог событий в книге заявок (в начале никаких заявок в книге нет). В логе есть события двух типов:

1. "ADD \(p\)" означает добавление новой заявки с ценой \(p\) и неизвестным направлением. Заявка не должна противоречить еще не удаленным заявкам в книге заявок.
2. "ACCEPT \(p\)" означает принятие существующего лучшего предложения с ценой \(p\) и неизвестным направлением.

Направления всех заявок (BUY или SELL) в логе утеряны. Не всегда по имеющимся данным можно однозначно восстановить эти направления. Посчитайте количество способов корректно восстановить направления ADD заявок так, что описанные условия всегда выполнены. Ответ может быть очень большим, поэтому выведите его по модулю \(10^9 + 7\). Если невозможно корректно восстановить направления, то выведите \(0\).

Назовем некоторое положительное целое число шикарным, если в его десятичной записи встречается не более \(3\) ненулевых цифр. Например, числа \(4\), \(200000\), \(10203\) шикарные, а числа \(4231\), \(102306\), \(7277420000\) — нет.

Задан отрезок \([L; R]\). Посчитайте количество таких шикарных чисел \(x\), что \(L \le x \le R\).

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

Вам дан массив \(a\) из \(n\) целых чисел и целое число \(k\) (\(2 \le k \le n\)), где элементы массива обозначаются как \(a_i\) (\(0 \le i < n\)). Выполните операцию \(z\) определённую ниже над \(a\) и выведите значение \(z(a,k)\) по модулю \(10^{9}+7\).

function z(array a, integer k):
    if length(a) < k:
        return 0
    else:
        b = empty array
        ans = 0
        for i = 0 .. (length(a) - k):
            temp = a[i]
            for j = i .. (i + k - 1):
                temp = max(temp, a[j])
            append temp to the end of b
            ans = ans + temp
        return ans + z(b, k)

Януш — бизнесмен. Он владеет компанией «Янушзекс», которая производит игры для школьников. Последним хитом Янушзекс является крутая игра для одного человека «Сделай единицу». Игроку дана последовательность из \(n\) целых чисел \(a_i\).

Разрешается выбрать любое подмножество из них и количество очков равно наибольшему общему делителю выбранных чисел. Игроку нужно выбрать наименьшее количество элементов, получив количество очков, равное \(1\). Теперь Януш интересуется, какое минимальное количество элементов нужно выбрать игроку в таком случае?

Рассмотрим некоторое множество различных символов \(A\) и некоторую строку \(S\), состоящую ровно из \(n\) символов, где каждый символ присутствует в \(A\).

Задан массив \(b\) из \(m\) целых чисел (\(b_1 < b_2 < \dots < b_m\)).

Разрешено проводить следующую операцию над строкой \(S\):

1. Выбрать некоторый корректный \(i\) и выставить \(k = b_i\);
2. Взять первые \(k\) символов \(S = Pr_k\);
3. Взять последние \(k\) символов \(S = Su_k\);
4. Заменить первые \(k\) символов \(S\) развернутой \(Su_k\);
5. Заменить последние \(k\) символов \(S\) развернутой \(Pr_k\).

Например, рассмотрим строку \(S =\) «abcdefghi» и \(k = 2\). \(Pr_2 =\) «ab», \(Su_2 =\) «hi». Развернутые \(Pr_2 =\) «ba», \(Su_2 =\) «ih». Следовательно, полученная \(S\) равна «ihcdefgba».

Данная операция может быть проведена произвольное количество раз (возможно, ноль). Любой \(i\) может быть выбран несколько раз в ходе проведения операций.

Назовем строки \(S\) и \(T\) равными тогда и только тогда, когда существует такая последовательность операций, которая преобразовывает строку \(S\) в строку \(T\). Для приведенного выше примера «abcdefghi» и «ihcdefgba» равны. Обратите внимание, что это подразумевает и \(S = S\).

Задача проста. Посчитайте количество различных строк.

Ответ может быть достаточно велик, поэтому посчитайте его по модулю \(998244353\).

Задано два целых числа \(l\) и \(r\) (\(l \le r\)). Ваша задача — посчитать сумму чисел от \(l\) до \(r\) (включая \(l\) и \(r\)) таких, что каждое число содержит не более \(k\) различных цифр, и вывести эту сумму по модулю \(998244353\).

Например, если \(k = 1\), тогда вам необходимо посчитать все числа от \(l\) до \(r\) такие, что каждое число содержит только одинаковые цифры. Для \(l = 10, r = 50\) ответ равен \(11 + 22 + 33 + 44 = 110\).

Орехус нашел строку \(s\), состоящую из латинских букв нижнего регистра. Орехус любознательный парень, поэтому ему стал интересен следующий вопрос: сколько существует строго возрастающих последовательностей \(p_1, p_2, \ldots, p_k\) таких, что:

1. Для каждого \(i\) (\(1 \leq i \leq k\)), \(s_{p_i} =\) 'a'.
2. Для каждого \(i\) (\(1 \leq i < k\)), существует \(j\), что \(p_i < j < p_{i + 1}\) и \(s_j =\) 'b'.

Удовлетворите любопытство Орехуса, или он расстроится.

Это число должно быть посчитано по модулю \(10^9 + 7\).

Пусть \(n\) — целое число. Рассмотрим все перестановки целых чисел от \(1\) до \(n\) в лексикографическом порядке. Объедините их в одну большую последовательность \(p\). Например, если \(n = 3\), то \(p = [1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 1, 2, 3, 2, 1]\). Длина этой последовательности будет \(n \cdot n!\).

Пусть \(1 \leq i \leq j \leq n \cdot n!\) — пара индексов. Мы называем последовательность \((p_i, p_{i+1}, \dots, p_{j-1}, p_j)\) подотрезком \(p\). Его длина определяется как количество элементов, то есть \(j - i + 1\). Его сумма определяется как сумма всех его элементов, то есть \(\sum_{k=i}^j p_k\).

Дано \(n\). Найдите количество подотрезков \(p\) длины \(n\), имеющих сумму \(\frac{n(n+1)}{2}\). Поскольку это число может быть большим, выведите его по модулю \(998244353\) (простое число).

Хасан любит различные игры, и недавно его заинтересовала игра под названием Супер-Бомбардир. В этой игре (которая довольно похожа на футбол) \(p\) игроков бьют пенальти. Победитель — это тот игрок, который забил наибольшее число голов. В случае ничьи, один из игроков, забивших наибольшее число голов, объявляется победителем равновероятно.

Игроки только закончили матч, и теперь ожидают результата. Однако закралась небольшая проблема! Судьи потеряли таблицу с счетом всех игроков! К счастью, до потери они успели посчитать сумму забитых голов, а также для каждого игрока они запомнили нижнюю границу на количество забитых им голов. Однако информация об этих границах конфиденциальна, поэтому Хасан смог узнать только свою нижнюю границу.

Согласно предоставленной информации, он знает, что его счет не меньше \(r\), а сумма счета всех игроков — \(s\).

Поэтому финальное состояние игры может быть записано в виде последовательности \(p\) целых чисел \(a_1, a_2, \dots, a_p\) (\(0 \le a_i\)) — счет игроков. Хасан — игрок номер \(1\), поэтому \(a_1 \ge r\). К тому же \(a_1 + a_2 + \dots + a_p = s\). Два состояния считаются различными, если существует такая позиция \(i\), что значение \(a_i\) различается в этих двух состояниях.

Еще раз, Хасан не знает точного счета игроков (он не знает и свой точный счет). Поэтому он считает, что вероятность получить любое финальное состояние игры одинакова.

Помогите Хасану найти вероятность его победы.

Можно показать, что она может быть представлена в форме \(\frac{P}{Q}\), где \(P\) и \(Q\) — неотрицательные целые числа и \(Q \ne 0\), \(P \le Q\). Сообщите значение \(P \cdot Q^{-1} \pmod {998244353}\).

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

Вам дано дерево \(T\), содержащее \(n\) вершин, пронумерованных от \(1\) до \(n\). Для каждого непустого \(X\), являющемся подмножеством вершин \(T\), определим \(f(X)\) как количество рёбер в минимальном по размеру поддереве \(T\), содержащем все вершины из \(X\).

Вам также дано целое число \(k\). Вам нужно вычислить сумму \((f(X))^k\) по всем непустым подмножествам вершин, то есть:

\(\) \sum\limits_{X \subseteq \{1, 2,\: \dots \:, n\},\, X \neq \varnothing} (f(X))^k. \(\)

Так как эта величина может быть очень большой, выведите её по модулю \(10^9 + 7\).

У Аюба был массив целых чисел \(a\) длины \(n\) и у этого массива было два необычных свойства:

• Все целые числа в этом массиве были от \(l\) до \(r\) (включительно).
• Сумма всех элементов в массиве делилась на \(3\).

К сожалению, Аюб потерял свой массив, но он помнит размер массива \(n\), а также числа \(l\) и \(r\), так что он попросил вас посчитать количество способов восстановить массив по этим данным.

Так как ответ может быть очень большим, выведите его по модулю \(10^9 + 7\) (то есть остаток при делении на \(10^9 + 7\)). В случае если не существует ни одного подходящего массива (Аюб что-то перепутал) — выведите \(0\).

Маленький Петя любит считать. Он хочет посчитать, сколько существует способов раскрасить прямоугольную клетчатую доску размера n × m (n строк, m столбцов) в k цветов. При этом раскраска должна обладать следующим свойством: для любой вертикальной прямой, проходящей по линиям сетки и делящей доску на две непустые части, количество различных цветов в обеих этих частях должно быть одинаковым. Помогите Пете посчитать количество таких раскрасок.

Задано неориентированное дерево из \(n\) вершин.

Некоторые вершины покрашены в один из \(k\) цветов, а некоторые не покрашены совсем. Гарантируется, что дерево содержит хотя бы одну вершину каждого из \(k\) цветов. Может быть ноль непокрашенных вершин.

Вы выбираете набор из ровно \(k - 1\) ребер и удаляете его из дерева. Дерево распадается на \(k\) связных компонент. Назовем набор хорошим, если ни в одной из полученных компонент не будет вершин различных цветов.

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

Ответ может быть довольно большим, поэтому выведите его по модулю \(998244353\).

Назовем массив \(b\) плохим если он содержит последовательный отрезок \(b_l, b_{l+1}, \dots, b_{r}\) нечетной длины больше \(1\) (\(l < r\) и \(r - l + 1\) нечетно) такой что \(\forall i \in \{0, 1, \dots, r - l\}\) \(b_{l + i} = b_{r - i}\).

Если массив не плохой, то он хороший.

Вам задан массив \(a_1, a_2, \dots, a_n\). Некоторые его элементы равны \(-1\). Посчитайте количество хороших массивов, которое вы можете получить, заменив все \(-1\) на какие-то числа от \(1\) до \(k\).

Так как ответ может быть большим, выведите его по модулю \(998244353\).

Девочка по имени Соня учится в научном лицее Королевства Кремляндия. Учитель информатики (любимого предмета Сони!) придумал для неё задачу.

Даётся массив \(a\) длины \(n\), состоящий только из чисел \(0\) и \(1\), а также число \(k\). Ровно \(k\) раз происходит следующее:

• Равновероятно выбираются два числа \(i\) и \(j\) такие, что (\(1 \leq i < j \leq n\)).
• Числа, стоящие на позициях \(i\) и \(j\), меняются местами.

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

Можно показать, что искомая вероятность или равна \(0\), или её можно представить как \(\dfrac{P}{Q}\), где \(P\) и \(Q\) — взаимно простые числа и \(Q \not\equiv 0~\pmod {10^9+7}\).

В первый класс школы в Нлогонии набрали \(n\) учеников. Директор хочет разделить их в два класса, каждый ученик должен оказаться ровно в одном из этих классов. Если в один класс попадут два школьника, имена которых начинаются с одной и той же буквы, то они будут слишком много болтать друг с другом (ведь наверняка у них много общего). Обозначим за \(x\) количество таких пар учеников в некотором разбиении на два класса. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми и учитываются один раз.

Например, если всего в классе \(6\) учеников — «olivia», «jacob», «tanya», «jack», «oliver» и «jessica», то:

• разделение на два класса («jack», «jacob», «jessica», «tanya») и («olivia», «oliver») даст \(x=4\) (\(3\) пары будут болтать в первом классе, \(1\) пара будет болтать во втором классе),
• разделение на два класса («jack», «tanya», «olivia») и («jessica», «oliver», «jacob») даст \(x=1\) (\(0\) пар будут болтать в первом классе, \(1\) пара будет болтать во втором классе).

Вам дан список из \(n\) имен. Какое минимальное значение \(x\) мы можем получить, распределив этих школьников на два класса?

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

Вам задан массив \(a_1, a_2, \dots, a_n\). Все \(a_i\) попарно различные.

Определим функцию \(f(l, r)\) следующим образом:

• создадим массив \(b_1, b_2, \dots, b_{r - l + 1}\), где \(b_i = a_{l - 1 + i}\);
• отсортируем массив \(b\) в порядке возрастания;
• результатом функции \(f(l, r)\) назовем значение \(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}\).

Посчитайте \(\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)\). Другими словами — сумму функций \(f\) для всех подотрезков массива \(a\) по модулю \(10^9+7\).

Определим функцию \(f(p)\) от перестановки \(p\) следующим образом. Пусть \(g_i\) — наибольший общий делитель (НОД) чисел \(p_1\), \(p_2\), ..., \(p_i\) (другими словами, НОД на префиксе длины \(i\)). Тогда \(f(p)\) равно числу различных значений среди \(g_1\), \(g_2\), ..., \(g_n\).

Пусть \(f_{max}(n)\) — максимальное значение \(f(p)\) среди всех перестановок \(p\) чисел \(1\), \(2\), ..., \(n\).

Вам дано число \(n\), подсчитайте число перестановок \(p\) чисел \(1\), \(2\), ..., \(n\) таких, что \(f(p)\) равно \(f_{max}(n)\). Так как ответ может быть большим, выведите остаток от деления этого числа на \(1000\,000\,007 = 10^9 + 7\).

Это первая подзадача задачи F. Единственные различия между этой и второй подзадачами — это ограничения на значение \(m\) и ограничение по времени. Вам нужно решить обе подзадачи, чтобы взламывать эту подзадачу.

Во вселенной всего есть \(n+1\) разных цветов, пронумерованных от \(0\) до \(n\). Есть полоска, длина которой \(m\) сантиметров, изначально покрашенная в цвет \(0\).

Алиса взяла кисть и начала разукрашивать полоску. Для каждого \(i\) от \(1\) до \(n\) в таком порядке она выбирает два числа \(0 \leq a_i < b_i \leq m\) такие, что отрезок \([a_i, b_i]\) сейчас покрашен одним цветом, и красит его в цвет \(i\).

Алиса выбрала такие отрезки, что сейчас каждый сантиметр имеет отличный от \(0\) цвет. Формально, отрезок \([i-1, i]\) покрашен в цвет \(c_i\) (\(c_i \neq 0\)). Каждый цвет, кроме \(0\), виден на полоске.

Посчитайте количество пар последовательностей \(\{a_i\}_{i=1}^n\), \(\{b_i\}_{i=1}^n\), которые дадут заданную полоску.

Так как это число может быть очень большим, выведите его по модулю \(998244353\).

Единственное отличие этой версии от усложнённой — это ограничения.

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

В плеере у Поликарпа хранится \(n\) песен, причем каждая из них характеризуется двумя параметрами: \(t_i\) и \(g_i\), где \(t_i\) — длительность песни в минутах (\(1 \le t_i \le 15\)), \(g_i\) — её жанр (\(1 \le g_i \le 3\)).

Поликарп хочет составить такой плейлист, чтобы всё время в пути от университета до дома, он мог слушать музыку и в момент прибытия домой плейлист кончился. Поликарп никогда не прерывает песни и всегда слушает их от начала и до конца. Таким образом, если он начал слушать \(i\)-ю песню, то на её прослушивание он потратит ровно \(t_i\) минут. Также Поликарп не любит, когда подряд играют две песни одинакового жанра или когда песни в его плейлисте повторяются.

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

На Moscow Workshops ICPC команды получают воздушные шарики за каждую задачу, которую они решили первыми. Команда MSU Red Panda получила так много шариков, что они не знали, что с ними делать. Тогда они придумали о них задачу.

Есть несколько шариков, всего не более \(10^6\), каждый покрашен в один из \(k\) цветов. Мы можем делать следующую операцию: выбрать \(k-1\) шариков \(k-1\) различных цветов, и перекрасить их все в оставшийся цвет. Мы можем выполнять данную операцию любое конечное число раз (в частности, мы можем выполнить очередную операцию только если существует по крайней мере \(k-1\) различных цветов среди шариков в данный момент).

Сколько различных конфигураций шариков мы можем получить? Играет роль только количество шариков каждого цвета, конфигурации, отличающиеся только порядком шариков, считаются одинаковыми. Так как это число может быть очень большим, выведите его по модулю \(998244353\).

Эта задача отличается от следующей исключительно наличием ограничения на равную длину всех чисел \(a_1, a_2, \dots, a_n\). На самом деле эта задача является подзадачей D2 из этого же контеста, и решение D2 решает эту подзадачу в том числе.

Команда ЛКШ-ат собралась совершить путешествие на подводной лодке. Цель их плавания — древний клад на затонувшем судне, лежащем на дне Великого Рыбинского моря. К сожалению, ребята не знают координаты судна, и поэтому обратились за помощью к потомственному магу Мишане. Он согласился помочь команде, но только если они решат его задачку.

Определим функцию, чередующую цифры двух чисел, \(f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)\), где \(a_1 \dots a_p\) и \(b_1 \dots b_q\) — цифры двух чисел в десятичной системе счисления, записанные без ведущих нулей.

Иными словами, функция \(f(x, y)\) перемешивает цифры чисел \(x\) и \(y\) выписывая их по очереди от младщих цифр к старшим, начиная с числа \(y\). Результат функции тоже строится справа налево (то есть от младших цифр к старшим). Если цифры одного из аргументов закончились, то выписываются оставшиеся цифры другого аргумента. Ознакомьтесь с примерами и формальным определением функции.

Например: \(\)f(1111, 2222) = 12121212\(\) \(\)f(7777, 888) = 7787878\(\) \(\)f(33, 44444) = 4443434\(\) \(\)f(555, 6) = 5556\(\) \(\)f(111, 2222) = 2121212\(\)

Формально:

• если \(p \ge q\), то \(f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q\);
• если \(p < q\), то \(f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q\).

Мишаня дал вам массив из \(n\) целых чисел \(a_i\). Все числа в этом массиве имеют равную длину (то есть состоят из одинакового количества цифр). Помогите ребятам посчитать \(\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)\) по модулю \(998\,244\,353\).

В магазине неподалеку продаются известные русские деревянные игрушки под названием «матрешки», и вы бы хотели приобрести несколько штук. В магазине продается \(n\) различных матрешек. Любая матрешка — это фигурка объема \(out_i\) с пустотой внутри объемом \(in_i\) (конечно, \(out_i > in_i\)).

У вас не так много свободного места в сумке, но, к счастью, вы знаете, что матрешки можно вкладывать друг в друга. Формально, назовем набор матрешек вкладываемым, если мы можем переупорядочить их таким образом, что первая матрешка вкладывается во вторую, вторая — в третью и так далее. Матрешка \(i\) вкладывается в матрешку \(j\), если \(out_i \le in_j\). Только последняя игрушка из вкладываемого набора будет занимать место в вашей сумке.

Назовем пустотой вкладываемого набора общий объем пустого места внутри данной структуры. Очевидно, что она равна \(in_{i_1} + (in_{i_2} - out_{i_1}) + (in_{i_3} - out_{i_2}) + \dots + (in_{i_k} - out_{i_{k-1}})\), где \(i_1\), \(i_2\), ..., \(i_k\) — индексы выбранных матрешек в порядке их вкладывания.

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

Вы хотели бы купить много матрешек, а потому выбираете достаточно большой вкладываемый поднабор. Но автора задачи сильно расстроит, если в вашей сумке будет потрачено зря слишком много места, поэтому вы выбираете достаточно большой вкладываемый поднабор, пустота которого минимально возможная среди всех достаточно больших поднаборов. И вот возник вопрос: как много различных поднаборов удовлетворяют всем требованиям (поднаборы достаточно большие, и нет другого достаточно большого поднабора с пустотой меньше заданного). Два поднабора считаются различными, если существует хотя бы один индекс \(i\) такой, что один поднабор содержит \(i\)-ю матрешку, а другой — нет.

Так как ответ может быть очень большим — выведите его по модулю \(10^9 + 7\).

Два любимых числа Наташи — это \(n\) и \(1\), а два любимых числа Саши — \(m\) и \(-1\). Однажды Саша и Наташа встретились и выписали все возможные массивы из \(n+m\) элементов, в которых \(n\) элементов равны \(1\), а другие \(m\) элементов равны \(-1\). Для каждого массива они посчитали его максимальную префиксную сумму, возможно пустую, равную \(0\) (т. е. если каждая непустая префиксная сумма меньше нуля, то она считается равной нулю). Более формально, обозначим за \(f(a)\) максимальную префиксную сумму массива \(a_{1, \ldots ,l}\) длины \(l \geq 0\). Тогда:

\(\)f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )\(\)

Теперь они хотят посчитать сумму максимальных префиксных сумм по всем выписанным массивам и просят вас в этом помочь. Так как эта сумма может быть очень большой, выведите её по модулю \(998\: 244\: 853\).

Вам задано \(n\) пар чисел: \((a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)\). Последовательность считается плохой, если она отсортирована в порядке неубывания по первым элементам или если она отсортирована в порядке неубывания по вторым элементам. Иначе последовательность считается хорошей. Примеры хороших и плохих последовательностей:

• \(s = [(1, 2), (3, 2), (3, 1)]\) — плохая, потому что последовательность первых элементов отсортирована: \([1, 3, 3]\);
• \(s = [(1, 2), (3, 2), (1, 2)]\) — плохая, потому что последовательность вторых элементов отсортирована: \([2, 2, 2]\);
• \(s = [(1, 1), (2, 2), (3, 3)]\) — плохая, потому что обе последовательности (последовательность первых элементов и последовательность вторых элементов) отсортированы;
• \(s = [(1, 3), (3, 3), (2, 2)]\) — хорошая, потому что обе последовательности (последовательность первых \(([1, 3, 2])\) и последовательность вторых элементов \(([3, 3, 2])\)) не отсортированы.

Посчитайте количество перестановок длины \(n\) таких, что после применения этой перестановки к последовательности \(s\) она станет хорошей последовательностью.

Перестановка \(p\) длины \(n\) это последовательность \(p_1, p_2, \dots , p_n\) состоящая из \(n\) различных чисел от \(1\) до \(n\) (\(1 \le p_i \le n\)). Если вы примените перестановку \(p_1, p_2, \dots , p_n\) к последовательности \(s_1, s_2, \dots , s_n\) вы получите последовательность \(s_{p_1}, s_{p_2}, \dots , s_{p_n}\). Например, если \(s = [(1, 2), (1, 3), (2, 3)]\) и \(p = [2, 3, 1]\), то \(s\) превратится \([(1, 3), (2, 3), (1, 2)]\).

В данной задаче вам задана последовательность \(a_1, a_2, \dots, a_n\), состоящая из \(n\) ненулевых целых чисел (то есть \(a_i \ne 0\)).

Перед вами стоит задача найти два числа:

1. количество таких пар индексов \((l, r)\) \((l \le r)\), что произведение \(a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r\) строго отрицательно;
2. количество таких пар индексов \((l, r)\) \((l \le r)\), что произведение \(a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r\) строго положительно.

Это усложненная версия задачи, в этой версии \(1 \le n \le 2\cdot10^5\). Вы можете взламывать эту задачу, если вы ее заблокировали. Но вы можете взламывать предыдущую версию задачи, только если вы заблокировали обе версии.

В задаче идёт речь о тесте из \(n\) вопросов. Каждый вопрос содержит \(k\) вариантов ответа, и только один из них правильный. Ответ на \(i\)-й вопрос это \(h_{i}\). Если ваш ответ на вопрос \(i\) равен \(h_{i}\), вы получите \(1\) балл, в противном случае вы получите \(0\) баллов за этот вопрос. В этой задаче значения \(h_1, h_2, \dots, h_n\) вам известны (заданы).

Однако, вы допустили ошибку в вашей программе! Расположим все \(n\) ответов на окружности по часовой стрелке. Из-за ошибки в вашей программе, они сдвигаются на один по циклу в направлении часовой стрелки.

Формально, ошибка двигает ответ на вопрос \(i\) к вопросу \(i \bmod n + 1\). Так она двигает ответ на вопрос \(1\) к вопросу \(2\), ответ на вопрос \(2\) к вопросу \(3\), ..., ответ на вопрос \(n\) к вопросу \(1\).

Назовем все \(n\) ответов вместе набором ответов. Всего есть \(k^n\) возможных наборов ответов.

Вас интересует количество наборов ответов удовлетворяющих следующему условию: после сдвига по часовой стрелки на \(1\), итоговое количество баллов нового набора ответов строго больше чем старого. Вам необходимо найти это количество по модулю \(998\,244\,353\).

Например, если \(n = 5\) и ваш набор ответов \(a=[1,2,3,4,5]\), он будет изменен вашей программой на \(a'=[5,1,2,3,4]\) из-за ошибки. Если набор правильных ответов равен \(h=[5,2,2,3,4]\), тогда набор ответов \(a\) получит \(1\) балл, а набор ответов \(a'\) получит \(4\) балла. Так как \(4 > 1\), набор ответов \(a=[1,2,3,4,5]\) удовлетворяет условию и должен быть посчитан.

Двумерный массив называется скобочным массивом, если в каждой клетки находится одна из двух возможных скобочек — «(» или «)». Путь по клеткам двумерного массива называется монотонным, если любые две последовательные клетки в пути имеют общую сторону, и при этом каждая клетка пути находится либо ниже, либо правее предыдущей.

Двумерный скобочный массив размером n × m называется правильным скобочным массивом, если любая строка, полученная выписыванием скобочек на каком-то монотонном пути из клетки (1, 1) в клетку (n, m), образует правильную скобочную последовательность.

Определим операцию сравнения двух правильных скобочных массивов (a и b) следующим образом. Пусть задан двумерный массив приоритетов (p) — двумерный массив, заполненный различными целыми числами от 1 до nm. Найдем такую позицию (i, j) в двумерном массиве, что a_i, j ≠ b_i, j. Если таких позиций несколько, выберем ту, где число p_i, j минимально. Если a_i, j = «(», то a < b, иначе a > b. Если позиция (i, j) не найдена, то массивы считаются равными.

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

Рассмотрим прямоугольную доску из \(h\) строк и \(w\) столбцов, на которой расположены костяшки домино. Каждая костяшка покрывает ровно две клетки доски, которые имеют общую сторону. Каждая клетка покрыта не более чем одной костяшкой.

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

Вам дано идеально сбалансированное расположение домино на доске. Найдите число способов разместить ноль или более дополнительных костяшек на этой доске, чтобы расположение осталось идеально сбалансированным. Выведите это число по модулю \(998\,244\,353\).

Недавно Иванушка-дурачок захотел стать умнее и поэтому начал изучать теорию вероятностей. Он считает, что уже достаточно хорошо понимает данную тему, и стал этим хвастаться перед всеми.

В качестве примера, Иванушка продемонстрировал окружающим концепцию случайного рисунка. Рисунок представляет собой клетчатое поле из \(n\) строкам и \(m\) столбцов, каждая клетка которого покрашена в белый или чёрный цвет. Иванушка считает, что рисунок случайный, если для любой клетки верно, что среди её соседей по стороне есть не более одной клетки такого же цвета, что и она.

Его братья быстро выяснили, что задумал Иванушка. Они долго пытались объяснить ему, что он, дурачок, все ещё плохо понимает, что такое случайность. Но Иванушка так и не поверил им, поэтому они попросили помощи у вас. Они хотят найти количество различных случайных (по мнению Иванушки) рисунков. Два рисунка называются различными, если существует клетка, которая покрашена в разные цвета на этих рисунках. Так как число таких картинок может быть достаточно большим, выведите его по модулю \(10^9 + 7\).

В ходе проведения очередной весенней уборки, Даниэль нашел старый калькулятор, который ему очень понравился. Однако кажется, что что-то в нем сломано. Когда он хочет посчитать \(1 + 3\) c помощью калькулятора, он получает \(2\) вместо \(4\). Но при вычислении \(1 + 4\) ответ получается правильный, \(5\). Озадаченный таким поведением, он вскрыл калькулятор и нашел разгадку: полные сумматоры стали полусумматорами!

Теперь, когда он хочет посчитать \(a + b\) при помощи калькулатора, он получает ксор-сумму \(a \oplus b\) (определение можно прочитать по ссылке: https://ru.wikipedia.org/wiki/Сложение_по_модулю_2).

Но как он уже заметил ранее, калькулятор иногда выдает правильные ответы. Поэтому его интересует, при данных \(l\) и \(r\) сколько существует таких пар целых чисел \((a, b)\), для которых выполняются следующие условия: \(\)a + b = a \oplus b\(\) \(\)l \leq a \leq r\(\) \(\)l \leq b \leq r\(\)

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

Рождество постучало в дверь, и наш главный герой, Боб, готовил захватывающий подарок для своего давнего второго лучшего друга Чарли. Поскольку ему не нравится шоколад, он решил вместо этого украсить дерево. Дерево Боба можно представить в виде неориентированного связного графа с \(n\) вершинами (пронумерованными от \(1\) до \(n\)) и \(n-1\) ребрами. Первоначально Боб поместил украшение с номером \(i\) на вершину \(i\) для каждого \(1 \le i \le n\). Однако, поскольку такая простая композиция получилась некрасивой, он решил немного переместить украшения. Формально Боб сделал следующие шаги:

• Сначала он выписал все \(n-1\) ребра в некотором порядке.
• Затем он рассмотрел все ребра один за другим в таком порядке. Для каждого ребра \((u, v)\) он поменял местами украшение вершины \(u\) с украшением вершины \(v\).

После этого Боб оказался довольным такой аранжировкой и пошел спать.

На следующее утро Боб просыпается, только чтобы узнать, что его прекрасная аранжировка разрушена! Прошлой ночью младший брат Боба, Бобо, бросил некоторые украшения на пол, когда играл с деревом. К счастью, украшения не были потеряны, поэтому Боб может восстановить дерево в кратчайшие сроки. Однако он полностью забыл, как дерево выглядело вчера. Поэтому, учитывая номера украшений, которые все еще на дереве, Боб хочет узнать количество возможных конфигураций дерева. Поскольку результат может быть довольно большим, Боб будет рад, если вы сможете вывести результат по модулю \(1000000007\) (\(10^9+7\)). Обратите внимание, что, возможно, не существует никаких возможных конфигураций.

Это сложная версия этой задачи. Единственное отличие в ограничении на \(n\) — длине входной строки. В этой версии, \(1 \leq n \leq 10^6\).

Определим правильную скобочную последовательность и ее глубину следующим образом:

• Пустая строка это правильная скобочная последовательность глубины \(0\);
• Если «s» это правильная скобочная последовательность глубины \(d\) тогда «(s)» это правильная скобочная последовательность глубины \(d + 1\);
• Если «s» и «t» это две правильные скобочные последовательности тогда их конкатенация «st» это правильная скобочная последовательность с глубиной равной максимальной из глубин \(s\) и \(t\).

Для (не обязательно правильной) скобочной последовательности \(s\) мы определяем ее глубину как максимальную глубину любой правильной скобочной последовательности, которая может быть получена с помощью удаления некоторых символов из \(s\) (возможно нуля). Например, скобочная последовательность \(s = \)«())(())» имеет глубину \(2\), потому что при удалении третьего символа мы получим правильную скобочную последовательность «()(())» глубины \(2\).

Дана строка \(a\), состоящая из символов '(', ')' и '?'. Рассмотрим все (не обязательно правильные) скобочные последовательности, получающиеся заменой всех символов '?' в строке \(a\) на '(' или ')'. Посчитайте сумму глубин всех таких скобочных последовательностей. Так как это число может быть очень большим, найдите его по модулю \(998244353\).

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

Введем определение функции \(f(x)\): \(\) \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{если } x \text{ четное} \\ x - 1 & \mbox{в противном случае } \end{matrix} \right. \end{matrix} \(\)

Можно заметить, что если мы выбираем некоторое число \(v\) и применяем к нему функцию \(f\), затем применяем функцию \(f\) к числу \(f(v)\), и так далее, то рано или поздно мы получим значение \(1\). Выпишем все промежуточные значения на пути от \(v\) до \(1\) и назовем все выписанные значения \(path(v)\). Например, \(path(1) = [1]\), \(path(15) = [15, 14, 7, 6, 3, 2, 1]\), \(path(32) = [32, 16, 8, 4, 2, 1]\).

Выпишем все \(path(x)\) для всех \(x\) от \(1\) до \(n\). Перед вами стоит задача: определить максимальное число \(m\) такое, что \(m\) встречается хотя бы в \(k\) различных \(path(x)\).

Иначе говоря, нужно найти такое максимальное \(y\), что \(\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k\).

Рассмотрим следующий эксперимент. У вас есть колода из \(m\) карт, ровно одна из них — джокер. \(n\) раз вы производите следующие действия: перемешиваете колоду, берете верхнюю карту, просматриваете ее и возвращаете ее в колоду.

Пусть \(x\) — количество раз, когда вы брали с вершины колоды джокера. Предполагая, что при каждом перемешивании колоды все \(m!\) перестановок карт равновероятны, чему равно математическое ожидание \(x^k\)? Выведите ответ по модулю \(998244353\).

Да, мы не смогли придумать новогоднюю легенду для этой задачи.

Перестановка длины \(n\) — это массив \(n\) целых чисел, таких что каждое целое число от \(1\) до \(n\) появляется в нем ровно один раз.

Элемент \(y\) перестановки \(p\) достижим из элемента \(x\), Если \(x = y\), или \(p_x = y\), или \(p_{p_x} = y\) и так далее.

Определим декомпозицию перестановки \(p\) следующим образом: сначала у нас есть перестановка \(p\), все элементы которой не помечены, и пустой список \(l\). Затем мы делаем следующее: пока хотя бы один элемент не помечен в \(p\), находим самый левый такой элемент, перечисляем все элементы, которые достижимы из него в порядке их появления в \(p\), помечаем все эти элементы, затем циклически сдвигаем список этих элементов так, чтобы максимум появился в первой позиции, и добавляем этот список как элемент в \(l\). После того, как все элементы помечены, \(l\) является результатом этой декомпозиции.

Например, если мы хотим построить декомпозицию \(p = [5, 4, 2, 3, 1, 7, 8, 6]\), мы делаем следующее:

1. изначально \(p = [5, 4, 2, 3, 1, 7, 8, 6]\) (жирным шрифтом выделены помеченные элементы), \(l = []\);
2. самый левый не помеченный элемент — \(5\); \(5\) и \(1\) достижимы из него, поэтому список, который мы хотим сдвинуть, — \([5, 1]\); нет необходимости сдвигать его, так как максимум уже является первым элементом;
3. \(p = [\textbf{5}, 4, 2, 3, \textbf{1}, 7, 8, 6]\), \(l = [[5, 1]]\);
4. самый левый не помеченный элемент — \(4\), список достижимых элементов из него — это \([4, 2, 3]\); максимум уже первый элемент, поэтому сдвигать его не нужно;
5. \(p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, 7, 8, 6]\), \(l = [[5, 1], [4, 2, 3]]\);
6. самый левый не помеченный элемент — \(7\), список достижимых элементов из него — это \([7, 8, 6]\); мы должны сдвинуть его, чтобы он стал \([8, 6, 7]\);
7. \(p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, \textbf{7}, \textbf{8}, \textbf{6}]\), \(l = [[5, 1], [4, 2, 3], [8, 6, 7]]\);
8. все элементы помечены, так что \([[5, 1], [4, 2, 3], [8, 6, 7]]\) — результат декомпозиции.

Определим новогоднее преобразование перестановки следующим образом: построим декомпозицию этой перестановки; затем отсортируем все списки в декомпозиции по возрастанию первых элементов (мы не меняем местами элементы в этих списках, только сами списки); затем объединим списки в один список, который становится новой перестановкой. Например, новогоднее преобразование \(p = [5, 4, 2, 3, 1, 7, 8, 6]\) строится следующим образом:

1. декомпозиция равна \([[5, 1], [4, 2, 3], [8, 6, 7]]\);
2. после сортировки, декомпозиция становится равна \([[4, 2, 3], [5, 1], [8, 6, 7]]\);
3. \([4, 2, 3, 5, 1, 8, 6, 7]\) — результат преобразования.

Назовем перестановку хорошей, если результат ее преобразования совпадает с самой перестановкой. Например, \([4, 3, 1, 2, 8, 5, 6, 7]\) это хорошая перестановка; а \([5, 4, 2, 3, 1, 7, 8, 6]\) плохая, так как результатом преобразования является \([4, 2, 3, 5, 1, 8, 6, 7]\).

Ваша задача состоит в следующем: при заданных \(n\) и \(k\) найти \(k\)-ю (лексикографически) хорошую перестановку длины \(n\).

Вы межгалактический хирург, и у вас есть инопланетный пациент. Для целей этой задачи мы будем моделировать тело этого пациента, используя прямоугольную сетку размером \(2 \times (2k + 1)\). Инопланетянин имеет \(4k + 1\) различных органов, пронумерованных целыми числами от \(1\) до \(4k + 1\).

У здоровых инопланетян органы устроены особым образом. Например, вот как будут расположены органы здорового инопланетянина, если смотреть сверху, для \(k = 4\):

Здесь E обозначает пустое место.

В общем случае у здорового инопланетянина первая строка содержит органы от \(1\) до \(2k + 1\) (в порядке слева направо) и вторая строка содержит органы от \(2k + 2\) до \(4k + 1\) (в порядке слева направо) и пустое место после этого, в конце второй строки.

Органы вашего пациента целы, и находятся внутри его тела, но они каким-то образом перемешались! Ваша задача, как межгалактического хирурга, состоит в том, чтобы вернуть все органы свои места. Все органы пришельца должны находиться в его теле в течение всей процедуры. Это означает, что в любой момент времени во время процедуры есть ровно одна ячейка (в сетке), которая пуста. Кроме того, вы можете перемещать органы только одним из следующих способов:

• Вы можете поменять пустую позицию E с любым органом непосредственно слева или справа от нее (если они существуют). Вы делаете это, перемещая рассматриваемый орган в пустое место;
• Вы можете поменять пустую позицию E с любым органом непосредственно сверху или снизу от нее (если они существуют). Это можно сделать только если пустая позиция в самой левой колонке, самой правой колонке или центральной колонке. Аналогично вы перемещаете рассматриваемый орган в пустое место.

Вашей задачей является получить последовательность шагов которые вы должны сделать при операции, чтобы вернуть все \(4k + 1\) органов пациента на правильные места. Если это сделать невозможно, вы должны сообщить об этом.

Напомним, что перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).

Последовательность \(a\) является подотрезком \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца. Обозначим подотрезок как \([l, r]\), где \(l, r\) — целые числа и \(1 \le l \le r \le n\). Это обозначает подотрезок, у которого убрали \(l-1\) элементов слева и \(n-r\) справа.

Для перестановки \(p_1, p_2, \ldots, p_n\) назовём рамочным подотрезком такой подотрезок индексов \([l,r]\), в котором \(\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l\). Например, у перестановки \((6, 7, 1, 8, 5, 3, 2, 4)\) некоторые из рамочных подотрезков: \([1, 2], [5, 8], [6, 7], [3, 3], [8, 8]\). В частности, подотрезок \([i,i]\) всегда является рамочным подотрезком для любого \(i\) от \(1\) до \(n\) включительно.

Для перестановки \(p\) определим счастье перестановки как количество таких пар \((l, r)\), что \(1 \le l \le r \le n\) и \([l, r]\) является рамочным подотрезком. Например, перестановка \([3, 1, 2]\) имеет счастье \(5\): Все подотрезки индексов кроме \([1, 2]\) являются рамочными.

Даны два целых числа \(n\) и \(m\). Джонгвон хочет найти суммарное счастье всех перестановок длины \(n\) по модулю простого числа \(m\). Обратите внимание, что всего существует \(n!\) (факториал \(n\)) различных перестановок длины \(n\).

Дан массив \(a\), состоящий из \(n\) целых чисел, найдите:

\(\)\max\limits_{1 \le i < j \le n} LCM(a_i,a_j),\(\)

где \(LCM(x, y)\) — это наименьшее положительное целое число, которое делится и на \(x\), и на \(y\). Например, \(LCM(6, 8) = 24\), \(LCM(4, 12) = 12\), \(LCM(2, 3) = 6\).

На другом этаже A.R.C. Markland-N, молодой человек Саймон "Ксенон" Джексон отдыхает, завершив свои работы по проекту быстрее запланированного (впрочем как всегда). Так как свободного времени достаточно много, он надевает свой легендарный хакерский "X" инстинкт и бежит сражаться против банд кибермира.

Его целью является сеть из \(n\) небольших банд. Их сеть состоит из ровно \(n - 1\) прямых соединений, каждое из которых связывает какие-то две банды вместе. Соединения устроены таким образом, что любые две банды соединены через последовательность прямых соединений.

Изучая данные, Ксенон понял, что банды используют для самозащиты следующую форму шифрования. Каждому соединению назначено целое число от \(0\) до \(n - 2\), таким образом, что все назначенные числа различны, а каждое число назначено какому-то соединению. Если атакующий пытается получить доступ к защищённым данным, то ему придётся прорваться через \(S\) слоёв с паролями, где \(S\) определяется как:

\(\)S = \sum_{1 \leq u < v \leq n} mex(u, v)\(\)

Здесь \(mex(u, v)\) обозначает наименьшее неотрицательное целое число, которое не встречается на соединениях на единственном простом пути между бандами \(u\) и \(v\).

Ксенон не знает каким образом числа были назначены соединениям, но это не проблема. Он собирается поручить своим AI перебрать и взломать все пароли, но перед этим он хочет знать чему равно наибольшее возможное значение \(S\), чтобы настроить AI наиболее эффективно.

Сейчас Ксенон ушёл писать скрипты для AI, и он собирается их закончить в течение двух часов. Не могли бы вы найти наибольшее значение \(S\) перед тем, как он вернётся?

Наш владелец Кафе JOE Миллер скоро примет участие в новом игровом телешоу «1 против \(n\)».

Игра проходит в несколько раундов, где в каждом раунде ведущий задаёт JOE и его соперникам один общий вопрос. Все участники отвечающие неправильно выбывают из игры. Шоу заканчивается, когда остаётся только JOE (мы считаем, что JOE никогда не отвечает на вопрос неверно!).

Для каждого вопроса, на который отвечает JOE, если у него оставалось \(s\) (\(s > 0\)) соперников и из них \(t\) (\(0 \le t \le s\)) ответили неверно, то JOE получает \(\displaystyle\frac{t}{s}\) долларов. Ну а в следующем раунде у него будет уже \(s - t\) соперников.

JOE задумался, чему равен наибольший приз, который он может получить в лучшем случае. Однако шоу начинается достаточно скоро, и у него нет на это времени. Может быть вы сможете ответить на этот вопрос?

Ги-Мануэль и Тома планируют \(144\) кругосветных путешествия.

Вам дан простой взвешенный неориентированный связный граф из \(n\) вершин и \(m\) рёбер со следующим ограничением: не существует простого цикла (т. е. цикла, проходящего через каждую вершину не больше раза) длины больше \(3\), проходящего через вершину \(1\). Стоимостью пути (необязательно простого) в этом графе является XOR весов всех рёбер, входящих в этот путь, причём каждое ребро считается столько, сколько раз через него проходит путь.

Однако, путешествия стоимостью \(0\) их не устраивают.

Вы можете выбрать любое подмножество рёбер, инцидентных вершине \(1\), и удалить их. Сколько существует таких множеств, что при их удалении в полученном графе нет нетривиального цикла (необязательно простого) стоимостью \(0\), проходящего через вершину \(1\)? Цикл называется нетривиальным, если существует ребро, через которое он проходит нечётное количество раз. Так как ответ может быть большим, выведите его по модулю \(10^9+7\).