# 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.

#### Input

The first line contains the temlate of length **len** (**1** ≤ **len** ≤ `10`

). The second line contains the number of queries ^{6}**m** (**1** ≤ **m** ≤ `10`

). Each of the next ^{5}**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**.

lld 4 1 1 2 1 2 3 2 2 d 1 1 3

2 1 2