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

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

Входные данные

В первой строке находится шаблон длины len (1 ≤ len ≤ 106). Во второй строке натуральное число m (1 ≤ m ≤ 105) - количество запросов. Далее следует m строк, каждая из которых состоит либо из трех натуральных чисел 1liri (1 ≤ li ≤ ri ≤ len) начало и конец подстроки, либо запрос на изменение шаблона, который состоит из двух натуральных чисел и символа: 2 x c, где x - номер изменяемого элемента, с - новый символ.

Выходные данные

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