Следствие ведут колобки
Немногие знают, что всем известные колобки любили придумывать различные комбинации и пароли, когда им было скучно. Для создания пароля они использовали неизвестный алфавит, кроме того, в пароле могли присутствовать только первые по порядку цифры и буквы (то есть, если они хотят создать пароль, в котором будет три буквы и две цифры, то это будут обязательно первые буквы алфавита - A, B, C и две первые цифры - 1, 2). Также они создали шаблон - строку, состоящую только из символов 'l' и 'd': "l" - в пароле на этом месте будет буква и "d" - цифра. Паролем может быть любое слово, состоящее только из букв и цифр и, которое подходит под подстроку шаблона.
Теперь они хотят узнать, сколько различных паролей для заданной подстроки некоторого шаблона они смогут придумать.
Входные данные
В первой строке находится шаблон длины len (1 ≤ len ≤ 10^6). Во второй строке натуральное число m (1 ≤ m ≤ 10^5) - количество запросов. Далее следует m строк, каждая из которых состоит либо из трех натуральных чисел 1 l[i] r[i] (1 ≤ l[i] ≤ r[i] ≤ len) начало и конец подстроки, либо запрос на изменение шаблона, который состоит из двух натуральных чисел и символа: 2 x c, где x - номер изменяемого элемента, с - новый символ.
Выходные данные
Для каждого запроса с номером 1 выведите в отдельной строке число – количество возможных паролей для данной подстроки шаблона. Так как ответ может быть очень большим, выведите его по модулю 10^9 + 7.