eolymp
bolt
Try our new interface for solving problems
Məsələlər

Следствие ведут колобки

Следствие ведут колобки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB
prb4484

Немногие знают, что всем известные колобки любили придумывать различные комбинации и пароли, когда им было скучно. Для создания пароля они использовали неизвестный алфавит, кроме того, в пароле могли присутствовать только первые по порядку цифры и буквы (то есть, если они хотят создать пароль, в котором будет три буквы и две цифры, то это будут обязательно первые буквы алфавита - A, B, C и две первые цифры - 1, 2). Также они создали шаблон - строку, состоящую только из символов 'l' и 'd': "l" - в пароле на этом месте будет буква и "d" - цифра. Паролем может быть любое слово, состоящее только из букв и цифр и, которое подходит под подстроку шаблона.

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

Giriş verilənləri

В первой строке находится шаблон длины len (1len10^6). Во второй строке натуральное число m (1m10^5) - количество запросов. Далее следует m строк, каждая из которых состоит либо из трех натуральных чисел 1l[i]r[i] (1l[i]r[i]len) начало и конец подстроки, либо запрос на изменение шаблона, который состоит из двух натуральных чисел и символа: 2 x c, где x - номер изменяемого элемента, с - новый символ.

Çıxış verilənləri

Для каждого запроса с номером 1 выведите в отдельной строке число – количество возможных паролей для данной подстроки шаблона. Так как ответ может быть очень большим, выведите его по модулю 10^9 + 7.

Nümunə

Giriş verilənləri #1
lld
4
1 1 2
1 2 3
2 2 d
1 1 3
Çıxış verilənləri #1
2
1
2
Müəllif Александр Бурков
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года