Investigation by koloboks#4484
Few people know that the famous Koloboks loved to come up with different combinations and passwords when they were bored. To create a password they use an unknown alphabet, moreover, the password can contain only the first numbers and letters in order (if they want to create a password with three letters and two digits, it will be the first letters in the alphabet A, B, C and two first digits 1, 2). They created a template - a string consisting of only symbols 'l' and 'd': "l" - the password will contain a letter in this place, and "d" - a digit. The password is any word consisting of letters and digits only that fits a pattern.
Now they want to know how many different passwords for the specified substring of a pattern they can create.
The first line contains the template of length (1 \leq len \leq 10^6). The second line contains the number of queries (1 \leq m \leq 10^5). Each of the next lines contains either three integers 1 l_i r_i (1 \leq l_i \leq r_i \leq len) - the beginning and the end of the substring, or the query to update a template: two numbers and a letter: 2 , where is the index of changed element, is a new symbol.
For each query with number 1 print in a separate line the number of possible passwords for a given template. The answer can be big, so print it by modulo 10^9 + 7.
Example 1