eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB
prb4484

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
lld
4
1 1 2
1 2 3
2 2 d
1 1 3
Вихідні дані #1
2
1
2
Автор Олександр Бурков
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року