Слідство ведуть колобки#4484
Мало хто знає, що усім відомі колобки любили придумувати різноманітні комбінації та паролі, коли їм було нудно. Для створення пароля вони використовували невідомий алфавіт, крім того у паролі могли бути присутніми лише перші по порядку цифри та букви (тобто, якщо вони хочуть створити пароль, у якому буде три букви та дві цифри, то це будуть обов'язково перші букви алфавіту - A, B, C та дві перші цифри – 1, 2). Також вони створили шаблон – рядок, який складається лише із символів 'l' та 'd': "l" – у паролі на цьому місці буде буква і "d" – цифра. Паролем може бути довільне слово, яке складається лише з букв та цифр і яке підходить під підрядок шаблону.
Тепер вони хочуть дізнатися, скільки різних паролів для заданого шаблону та підрядка вони зможуть придумати.
У першому рядку знаходиться шаблон довжини (1 \leq len \leq 10^6). У другому рядку натуральне число (1 \leq m \leq 10^5) - кількість запитів. Далі йде рядків, кожен з яких складається або з трьох натуральних чисел 1 l_i r_i (1 \leq l_i \leq r_i \leq len) початок та кінець підрядка, або запит на зміну шаблону, який складається з двох натуральних чисел та символу: 2 , де - номер змінюваного елементу, – новий символ.
Для кожного запиту з номером 1 виведіть у окремому рядку число – кількість можливих паролів для заданого підрядка шаблону. Так як відповідь може бути дуже великою, виведіть її по модулю 10^9 + 7.
Приклад 1