Investigation by koloboks
A 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.
Input
The first line contains the temlate of length len (1 ≤ len ≤ 10^6). The second line contains the number of queries m (1 ≤ m ≤ 10^5). Each of the next m lines contains either three integers 1 l[i] r[i] (1 ≤ l[i] ≤ r[i] ≤ len) - the beginning and the end of the line, or the query to update a template: two numbers and a letter: 2 x c, where x is the index of changed element, с is a new symbol.
Output
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.