дп

Сейчас \(3000\)-ый год,и Беси - первая корова в космосе. Во время своего путешествия между звёздами, она обнаружила числовую прямую с \(N\) (\(2 \leq N \leq 5 \cdot 10^5\)) точками, пронумерованными от \(1\) до \(N\). Все точки изначально белые. Она может выполнять следующую операцию любое количество раз.

• Выбрать позицию \(i\) среди чисел на числовой прямой и положительное целое число \(x\). Затем покрасить все точки в интервале \([i, i + x - 1]\) в красный цвет и все точки в интервале \([i + x, i + 2x - 1]\) в синий цвет. Все выбранные интервалы должны быть не соединёнными (т.е. в интервале \([i, i + 2x - 1]\) не может быть точек ранее покрашенных в красный или синий цвет). Весь интервал должен попадать целиком в числовую прямую (т.е. \(1 \leq i \leq i + 2x - 1 \leq N\)).

Фермер Джон даёт Беси строку \(s\) длины \(N\), состоящую из символов \(R\), \(B\), \(X\). Строка представляет предпочитаемую ФД раскраску для каждой точки: \(s_i=R\) означает, что \(i\)-ая точка должна быть выкрашена в красный цвет, \(s_i = B\) означает, что \(i\)-ая точка должна быть выкрашена в синий цвет, а \(s_i = X\) означает, что нет ограничений на цвет \(i\)-ой точки.

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

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строка "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiebessie».

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

Вычисление \(B(s)\) – интересная задача, но фермеру Джону интересно решение еще более интересной задачи: дана строка длины \(t\) не более \(3\cdot 10^5\), состоящих только из символов a-z, вычислить сумму \(B(s)\) по всем непрерывным подстрокам \(s\) строки \(t\).

**Примечание. Ограничение по времени для этой задачи составляет 4 секунды, что в два раза больше, чем по умолчанию. Ограничение по памяти для этой задачи составляет 512 МБ, вдвое больше, чем по умолчанию.**

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строка "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiebessie».

Дана строка \(s\), пусть \(B(s)\) представляет собой максимальное количество повторяющихся копий. из «bessie» можно получить, удалив ноль или более символов из \(s\). В приведенном выше примере \(B(\)"bqessiyexbesszieb"\() = 2\). Кроме того, учитывая строка \(t\), пусть \(A(t)\) представляет собой сумму \(B(s)\) по всем непрерывным подстроки \(s\) строки \(t\).

У фермера Джона есть строка \(t\) длины не более \(2\cdot 10^5\), состоящая только из символов a-z. Пожалуйста, рассчитайте \(A(t)\) и как \(A(t)\) изменится после \(U\) (\(1\le U\le 2\cdot 10^5\)) обновлений, каждое из которых изменяет символ \(t\). Обновления являются кумулятивными.

**Замечание: Время на тест для этой задачи 5s, в 2.5 больше чем по умолчанию. Ограничение по памяти в этой задаче 512MB, в два раза больше чем по умолчанию.**

У Беси есть \(N\) (\(1\le N\le 18\)) бассейнов маны, \(i\)-ый из которых аккумулирует \(m_i\) маны в секунду (\(1\le m_i\le 10^8\)). Бассейны соединены набором \(M\) (\(0\le M\le N(N-1)\)) двунаправленных ребер \((a_i,b_i,t_i)\), обозначающих, что из бассейна \(a_i\) она может перебраться в бассейн \(b_i\) за \(t_i\) секунд (\(1\le a_i, b_i\le N\), \(a_i\neq b_i\), \(1\le t_i\le 10^9\)). Когда Беси находится в бассейне, она может собрать все маны, сохранённые в этом бассейне, опустошая его. В момент времени \(0\) все бассейны с маной пусты. Беси может выбрать с какого бассейна стартовать.

Ответьте на \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый указан двумя целыми числами \(s\) и \(e\) (\(1\le s\le 10^9\), \(1\le e\le N\)). Для каждого запроса определите максимальное количество маны, которую Беси может собрать за \(s\) секунд, оказавшись в бассейне \(e\) в конце \(s\)-ой секунды.

Фермер Джон выписал \(N\) (\(1\le N\le 300\)) цифр на кусках бумаги. Для каждого \(i\in [1,N]\), \(i\)-ый кусок бумаги содержит цифру \(a_i\) (\(1 \leq a_i \leq 9\)).

У коров есть два любимых целых числа \(A\) и \(B\) (\(1\le A\le B< 10^{18}\)) и они хотят, чтобы Вы ответили на \(Q\) (\(1\le Q\le 5\cdot 10^4\)) вопросов. Для \(i\)-го вопроса коровы должны идти слева направо по кускам бумаги \(l_i\dots r_i\) (\(1\le l_i\le r_i\le N\)), поддерживая изначально пустую кучу кусков бумаги. Для каждого куска бумаги, они или добавляют его в вершину кучи, или в дно кучи или никуда. В конце они читают цифры на кусках бумаги из кучи, сверху ко дну формируя целое число. Среди всех \(3^{r_i-l_i+1}\) способов для коров сделать выбор в этом процессе, посчитайте количество способов таких, что результат будет целым числом в интервале \([A,B]\) включительно и выведите это число по модулю \(10^9+7\).

Имеется \(N\) пастбищ (\(2 \le N \le 2\cdot 10^5\)), соединённых \(N-1\) дорогой, так что ои образуют дерево. Перемещение по каждой дороге занимает одну секунду. В начале на каждом пастбище 0 травы, трава на \(i\)-ом пастбище растёт со скоростью \(a_i\) (\(1\le a_i\le 10^8\)) единиц в секунду. Фермер Джон вначале находится в пастбище 1 и должен удобрить траву на каждом пастбище. Если он посещает пастбище, в котором \(x\) единиц травы, он должен потратить \(x\) единиц удобрений. Удобрять требуется только при первом посещении пастбища и удобрение пастбища занимает 0 единиц времени.

Ввод содержит дополнительный параметр \(T\in \{0,1\}\).

• Если \(T=0\), ФД должен завершить путь в пастбище 1.
• Если \(T=1\), ФД может завершить путь в любом пастбище.

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

Определите максимальное \(K\le N-1\) такое, что существует подпоследовательность subsequence \(a_0,a_1,\ldots,a_{K}\) чисел \(p\) таких, что для всех \(1\le j\le K\), \(a_{j - 1} < a_j\) если j-ый символ в строке есть U, и \(a_{j - 1} > a_j\), если \(j\)-ый символ в строке есть D.

Беси играет в такую игру. Игра начинается с последовательности из \(N\) (\(2\le N\le 262,144\)) положительных целых чисел \(a_1,a_2,\ldots,a_N\), каждое в интервале \(1\ldots 10^6\). За один ход Беси может взять два соседних числа и заменить их на число, большее, чем максимум из этих двух чисел (например, соседнюю пару \((5,7)\) на \(8\)). Игра заканчивается после \(N-1\) ходов, после которых остаётся только одно число. Цель игры - минимизировать это финальное число.

Ваша задача сыграть оптимально не только для \(a\), но и для всех непрерывных подпоследовательностей \(a\).

Выведите сумму минимально возможных финальных чисел для всех \(\frac{N(N+1)}{2}\) непрерывных подпоследовательностей \(a\).

Беси играет в такую игру. Игра начинается с последовательности из \(N\) (\(2\le N\le 262,144\)) положительных целых чисел \(a_1,a_2,\ldots,a_N\), каждое в интервале \(1\ldots 10^6\). За один ход Беси может взять два соседних числа и заменить их на число, большее, чем максимум из этих двух чисел (например, соседнюю пару \((5,7)\) на \(8\)). Игра заканчивается после \(N-1\) ходов, после которых остаётся только одно число. Цель игры - минимизировать это финальное число.

Ваша задача сыграть оптимально не только для \(a\), но и для всех непрерывных подпоследовательностей \(a\).

Выведите сумму минимально возможных финальных чисел для всех \(\frac{N(N+1)}{2}\) непрерывных подпоследовательностей \(a\).

1. \(\times d\), где \(d\) это цифра в интервале \([0,9]\)
2. \(+s\), где \(s\) это строка, обозначающая имя переменной. В программе все переменные различны.

Результат выполнения программы определяется как выражение - результат выполнения всех инструкций в порядке ввода , начиная с \(0\). Например, результаты выполнения программы \([\times 3,+x,+y,\times 2,+z]\) есть выражение \((0\times 3+x+y)\times 2+z=2\times x+2\times y+z\). При выполнении различные программы могут формировать одни и те же выражения. Например, исполнение программы \([+w,\times 0,+y,+x,\times 2,+z, \times 1]\) также в результате даёт выражение \(2\times x+2\times y+z\).

У Беси и Эльзы есть по программе из \(N\) (\(1\le N\le 2000\)) инструкций. Они объединяют инструкции этих программ, чтобы получить новую программу длиной \(2N\). Заметим, что всего имеется \(\frac{(2N)!}{N!\times N!}\) способов объединить программы, но но не все из этих программ дадут различные результаты.

Вычислите количество различных выражений, которые могут быть получены исполнением объединённых программ Беси и Эльзы по модулю \(10^9+7\).

Каждый ввод состоит из \(T\) (\(1\le T\le 10\)) тестов, которые требуется решать независимо. Гарантируется, что сумма \(N\) во всех \(T\) тестах не превысит \(2000\).

Вычислите максимальное количество единиц металла \(N\), которое может получить Беси после некоторой серии трансформаций.

• Если высоты соседних стогов сена отличаются ровно на 1, она может переместить верхний тюк сена с более высокого стога на менее высокий.

Сколько конфигураций по модулю \(10^9+7\) можно получить после выполнения данной операции конечное число раз? Две конфигурации рассматриваются как одна и та же если для всех \(i\) каждый стог сена содержит одно и тоже количество тюков в обоих стогах.

123
456
789

Беси может нажимать одну клавишу, две клавиши одновременно (имеющие общую сторону, всего 12 комбинаций), 4 клавиши одновременно, которые формируют квадрат (1245, 2356, 4578, or 5689).

Например, если телефонный номер 123659874, она может сэкономить время следующим образом:

1. Нажать 1 и 2 одновременно.
2. Нажать 3.
3. Нажать 6, 5, 9, 8 одноврменно.
4. Нажать 7 и 4 одновременно.

Однако при нажатии нескольких клавиш одновременно, цифры могут могут записаться в произвольном порядке. Например, после последнего нажатия (7 и 4 одновременно) может получиться 123596847 или 213659874

По заданной последовательности цифр, вычислите количество телефонных номеров, которые она может набрать, по модулю \(10^9+7\).

**Замечание: Время на тест для этой задачи 4s, в два раза больше чем обычно..**

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

Имеется также дополнительное ограничение: подарок может быть переназначен корове, если он изначально был назначен корове такого же типа (Holstein или Guernsey)). Задано \(Q\) (\(1\le Q\le \min(10^5,2^N)\))длин \(N\) строк пород для каждой из них вычислите количество переназначений, соответствующих ей.

Коровы хотят, чтобы ФД сделал \(\frac{N(N+1)}{2}\) групповых фоток по одной для каждой непрерывной подпоследовательности коров.

Однако ФД имеет свои соображения как выстроить коров. В частности, он отказывается делать фотку подпоследовательности коров, если она не формирует палиндром, это означает, что порода \(i\)-ой коровы от левого конца фотки должна совпадать с породой \(i\)-ой коровы от начала фотки, для всех положительных \(i\) меньше либо равных длины подпоследовательности. Каждая корова имеет породу Guernsey или Holstein.

Для каждой из \(\frac{N(N+1)}{2}\) непрерывных подпоследовательностей построения посчитайте минимальное количество транспозиций, с помощью которых можно реорганизовать эту подпоследовательность в палиндром или \(-1\), если это сделать невозможно. Одна транспозиция заключается во взятии двух соседних коров подпоследовательности и обмене их. Вывод - сумма всех таких количеств.

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

Ферма Джона может быть представлена как ориентированный взвешенный граф, с дорогами (дугами), соединяющими различные вершины и вес каждой дуги есть время, которое требуется чтобы проехать по этой дороге. Каждый день Беси любит путешествовать из амбара (вершина \(1\)) в поле (вершина \(N\)), используя ровно \(K\) дорог и хочет добраться до поля как можно быстрее при этих ограничениях. Однако, в некоторой точке, прекращается поддержка дорог и они начинают ломаться одна за другой, становясь непроходимыми. Помогите Беси определить кратчайший путь от амбара до поля во все моменты времени.

Формально, мы начинаем с полного взвешенного ориентированного графа из \(N\) вершин (\(1\le N\le 300\)) и \(N^2\) дуг: одна дуга для каждой пары \((i, j)\) \(1 \le i, j \le N\), заметим, что имеется \(N\) петель (дуг из \(i\) в \(i\)). После каждого удаления выведите минимальный вес из всех путей из \(1\) в \(N\), проходящих ровно \(K\) (необязательно различных) дуг \(2\le K\le 8\)). Заметим, что после \(i\)-го удаленя в графе остаётся \(N^2-i\) дуг.

Вес пути определяется как сумма весов всех дуг в пути. Заметим, что путь может содержать множество вхождений одних и тех же дуг, и одних и тех же вершин, включая \(1\) и \(N\).

У Беси \(N\) (\(1 \le N \le 2000\)) друзей. Однако они разные! Друг \(i\) имеет счёт популярности \(P_i\) (\(1 \le P_i \le 2000\)), и Беси хочет максимизировать сумму популярности друзей, которые пойдут с ней. Друг \(i\) пойдёт с ней только если она даст ему \(C_i\) (\(1 \le C_i \le 2000\)) "moonies". Друг \(i\) также может сделать скидку в \(1\) "mooney", если она даст ему \(X_i\) (\(1 \le X_i \le 2000\)) мороженых. Беси может получить сколько угодно скидок.

У Беси есть \(A\) moonies и \(B\) мороженых (\(0 \le A, B \le 2000\)). Помогите ей определить максимальную сумму популярностей, которую она может добиться, если потратит mooney и мороженое оптмально.

Сначала все \(N\) коров (\(2\le N\le 10^5\)) стоят в ряд, корова \(i\) стоит на позиции \(i\). Последовательность перемещений в танце задаётся \(K\) (\(1\le K\le 2\cdot 10^5\)) парами позиций \((a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})\). В каждую минуту \(i = 1 \ldots K\) танца, коровы в позициях \(a_i\) и \(b_i\) меняются позициями. Аналогичные \(K\) обменов произойдут в минуты \(K+1 \ldots 2K\), затем в минуты \(2K+1 \ldots 3K\), и т.д. до истечения \(M\) минут (\(1\le M\le 10^{18}\)) Другими словами

• В минуту \(1\), коровы в позициях \(a_1\) и \(b_1\) меняются позициями.
• В минуту \(2\), коровы в позициях \(a_2\) и \(b_2\) меняются позициями.
• ...
• В минуту \(K\), коровы в позициях \(a_{K}\) и \(b_{K}\) меняются позициями.
• В минуту \(K+1\), коровы в позициях \(a_{1}\) и \(b_{1}\) меняются позициями.
• В минуту \(K+2\), коровы в позициях \(a_{2}\) и \(b_{2}\) меняются позициями.
• и т.д. ...

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

Замечание: время на тест удвоено.

По сигналу Фермера Джона некоторые из коров образуют пары так, что

• Каждая пара состоит из коров пород Holstein \(h\) и Guernsey \(g\) чьи положения не более чем на \(K\) друг от друга (\(1\le K\le 10^9\)); то есть, \(|x_h-x_g|\le K\).
• Каждая корова или часть какой то пары, или не входит ни в какую пару.
• Разбиение на пары является максимальным если никакие из оставшихся коров не могут образовать пару.

Определите диапазон возможных сумм весов коров не попавших в пары, а именно

• Если \(T=1\), вычислите минимально возможную сумму весов неспаренных коров.
• Если \(T=2\), вычислите максимально возможную сумму весов неспаренных коров.

Эльза старается угадать это число. Она может задавать вопросы вида \(i\) больше или меньше?" для некоторого \(i\) от \(1\) до \(N\) включительно. Беси отвечает "HI!" если \(i\) больше чем \(x+0.5\), и "LO!", если \(i\) меньше чем \(x+0.5\).

Эльза работает в соответствии со следующей стратегией. Она создала список из \(N\) чисел, где каждое число от \(1\) до \(N\) встречается ровно один раз (другими словами, этот список является перестановкой размера \(N\).). Затем она идёт по этому списку называя числа для угадывания из него по порядку. Однако она пропускает все бесполезные запросы. Так если Эльза должна спросить число \(i\) а ранее она спрашивала число \(j < i\) такое, что Беси ответила "HI!", Эльза не спрашивает \(i\), а переходит к следующему числу в списке. Аналогично, если она ранее спрашивала про число \(j > i\), на которое Беси ответила "LO!", Эльза также пропускает это число \(i\) и переходит к следующему в списке. Можно доказать, что используя эту стратегию, Эльзая всегда уникально определит \(x\) вне зависимости от перестановки, которую она создаст.

Если мы сконкатенируем все ответы Беси "HI" или "LO" в одну строку \(S\), количество раз которое Беси ответит "HILO" есть количество подстрок длины \(4\) в строке \(S\), которые равны "HILO".

Беси знает, что Эльза использует эту стратегию и даже уже выбрала число \(x\), однако она не знает, какую перестановку использует Эльза. Ваша задача - вычислить сумму количеств раз, которые Беси скажет "HILO" для всех перестановок, которые Эльза может использовать - по модулю \(10^9+7\).