Слідство ведуть колобки
Мало хто знає, що усім відомі колобки любили придумувати різноманітні комбінації та паролі, коли їм було нудно. Для створення пароля вони використовували невідомий алфавіт, крім того у паролі могли бути присутніми лише перші по порядку цифри та букви (тобто, якщо вони хочуть створити пароль, у якому буде три букви та дві цифри, то це будуть обов'язково перші букви алфавіту - 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.