İstintaqı aparan koloboklar
Çox az adam bilir ki, hamıya məlum olan koloboklar darıxdıqları zaman müxtəlif kombinasiyalar və parollar uydurmağı sevirdilər. Parol yaratmaq üçün onlar naməlum əlifbadan istifadə edirdilər, üstəlik parolda yalnız sırayla ilk rəqəmlər və hərflər ola bilərdi (yəni, əgər onlar üç hərf və iki rəqəm olan parol yaratmaq istəsələr, bu mütləq əlifbanın ilk hərfləri - A, B, C və ilk iki rəqəm - 1, 2 olacaq). Həmçinin onlar bir şablon yaratdılar - yalnız 'l' və 'd' simvollarından ibarət olan bir sətir: "l" - parolda bu yerdə hərf olacaq və "d" - rəqəm. Parol yalnız hərflər və rəqəmlərdən ibarət olan və şablonun alt sətirinə uyğun gələn istənilən söz ola bilər.
İndi onlar müəyyən edilmiş şablon və alt sətir üçün neçə fərqli parol uydura biləcəklərini bilmək istəyirlər.
Giriş məlumatları
Birinci sətirdə uzunluğu len (1 ≤ len ≤ 10^6) olan şablon var. İkinci sətirdə təbii ədəd m (1 ≤ m ≤ 10^5) - sorğuların sayı. Daha sonra m sətir gəlir, hər biri ya üç təbii ədəddən ibarətdir 1 l[i] r[i] (1 ≤ l[i] ≤ r[i] ≤ len) alt sətirin başlanğıcı və sonu, ya da şablonun dəyişdirilməsi sorğusu, iki təbii ədəd və simvoldan ibarətdir: 2 x c, burada x - dəyişdirilən elementin nömrəsi, c – yeni simvol.
Çıxış məlumatları
Hər bir 1 nömrəli sorğu üçün ayrıca sətirdə verilmiş şablon alt sətiri üçün mümkün parolların sayını çıxarın. Cavab çox böyük ola biləcəyi üçün onu 10^9 + 7 moduluna görə çıxarın.