favorite We need a little bit of your help to keep things running, click on this banner to learn more

Investigation by koloboks

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.


The first line contains the temlate of length len (1len106). The second line contains the number of queries m (1m105). Each of the next m lines contains either three integers 1liri (1lirilen) - 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.


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.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
1 1 2
1 2 3
2 2 d
1 1 3
Output example #1
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013