Задача №113598. Сдвигай, считай, и снова
Пусть дан строчный латинский символ 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 1 , c 2 , ... , c k }, где i ≤ index c 1 < index c 2 < ... < index c k ≤ j , таких что символы подмножества, переставленные в некотором порядке, образуют палиндромом. Так как число может быть очень большим, выведите его по модулю 10 9 + 7 .
Два подмножества символов строки называются различными, если множества индексов их элементов различаются.
Строка называется палиндромом, если читается слева направо также, как справа налево.
Первая строка содержит два целых числа N и Q ( 1 ≤ N , Q ≤ 10 5 ) - длину строки и количество запросов соответственно. Вторая строка содержит одну строку S длины N , состоящую из строчных латинских символов. Каждая из последующих Q строк содержит запрос в формате, описанном в условии.
Для каждого запроса второго типа выведите одно целое число - ответ на данный запрос.
Решения, работающие при N ≤ 500 и Q ≤ 500 , будут оцениваться в 20 баллов.
Решения, работающие при условии, что все запросы являются запросами второго типа, оцениваются еще в 30 баллов.
3 5 aba 2 0 2 2 0 0 2 1 2 1 0 1 1 2 0 2
5 1 2 3
5 7 acdec 2 0 3 1 3 4 36 1 2 3 81 1 1 4 11 2 3 3 2 2 3 2 1 2
4 1 2 2