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 ≤ 106). The second line contains the number of queries m (1 ≤ m ≤ 105). Each of the next m lines contains either three integers 1liri (1 ≤ li ≤ ri ≤ 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 109 + 7.