Пусть дан строчный латинский символ c . Тогда операция shift ( c ) превращает c в следующий по порядку символ в алфавите. Например, shift (a) = b, shift (e) = f, shift (z) = a.

Дана строка S , состоящая из N строчных латинских символов (индексация с 0). Необходимо обработать Q запросов 2 типов:

"1 i j t": ко всем элементам строки с индексами в отрезке [i:j] применить t раз операцию shift .

"2 i j": найдите количество непустых подмножеств символов строки { c ₁ , c ₂ , ... , c _k }, где i ≤ index _{c 1} < index _{c 2} < ... < index _{c k} ≤ j , таких что символы подмножества, переставленные в некотором порядке, образуют палиндромом. Так как число может быть очень большим, выведите его по модулю 10 ⁹ + 7 .

Два подмножества символов строки называются различными, если множества индексов их элементов различаются.

Строка называется палиндромом, если читается слева направо также, как справа налево.

Дан граф из \(n\) вершин, раскрасьте его в минимально возможное число цветов так, чтобы никакие две вершины, соединенные ребром, не были одного цвета.

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

Для числа k рассмотрим все такие различные мультимножества положительных чисел, что их сумма в точности k . Например для k = 3 эти множества {1, 1, 1} , {1, 2} , {3} .

Интересностью числа назовем сумму кубов размеров всех различных мультимножеств. Например интересность числа k = 3 равна 3 ³ + 2 ³ + 1 ³ = 27 + 8 + 1 = 36 .

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

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

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

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

Когда-то в детстве дедушка рассказал Киму, что снаряд никогда не попадает в одну воронку дважды, так что координаты всех выстрелов попарно различны.

Вы когда-нибудь мечтали стать главным героем компьютерной игры? Главный герой этой истории, Бранимир, мечтает сейчас именно об этом.

Мир в мечте Бранимира состоит из N небоскребов, пронумерованных слева направо. Для i -го небоскреба, известна его высота H _i и количество золотых монет G _i на крыше этого небоскреба. Игра начинается с прыжка на любой из небоскребов и состоит из нескольких ходов. На каждом ходу Бранимир может прыгнуть на любой небоскрёб, находящийся справа от него, но так, чтобы высота нового небоскрёба была не меньше того небоскрёба, на котором сейчас сидит Бранимир. Оказавшись на крыше небоскреба, Бранимир собирает все золотые монеты на ней. Бранимир может закончить игру после любого количества шагов (возможно, нулевого), но он должен собрать не менее K золотых монет, чтобы перейти на следующий уровень.

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