Problem Description

Regular expressions are a useful tool for text processing. In the year 3022, you come across a Python program you wrote earlier to download images from an illustration sharing website. You are intrigued and decide to run it, but due to its age, the regular expression within it is corrupted. You need to restore this regular expression. However, the extent of the damage is quite severe...

Problem Description

Here, we only consider a subset of regular expressions:

• Single Character: A single character, which must be a lowercase letter or a digit.
• Unit Expression: A string of three characters in the form <x>-<y>, where <x> and <y> are single characters. Note: <x> and <y> must be of the same type, i.e., both digits or both lowercase letters. Additionally, the ASCII value of <x> must be strictly less than that of <y>. For example, 3-5 and a-d are valid, while 7-b, z-3, and 8-2 are invalid.
• Expression: A unit expression or single character enclosed in square brackets, such as [1-2], [0-9a-f], [a-chg-k]. Nested brackets are not allowed. An asterisk * or a plus + can follow the closing bracket (at most one, not both). For example, [3-5]*, [pixi-v]+.
• A valid regular expression consists of one or more expressions or single characters. For example, 0x[0-9af]*, 1[3-7]2345, 0[7-9]*1.

Given the corrupted regular expression with missing characters represented by question marks ?, you need to calculate how many possible original regular expressions exist. The answer may be very large, so take it modulo $1000000007$.

Input Format

A single line containing a string representing the corrupted regular expression.

Output Format

A single integer representing the number of possible solutions modulo $1000000007$.

Sample Input and Output

Sample Input #1

??

Sample Output #1

1296

Sample Input #2

?a?

Sample Output #2

1297

Sample Input #3

a?bc??

Sample Output #3

46730

Notes

• Sample #1: Both question marks can be any digit or letter, resulting in $36 \times 36 = 1296$ possible solutions.
• Sample #2: In addition to digits and letters, brackets can be added to form [a], resulting in $1297$ possible solutions.
• Sample #3: The tester did not provide an explanation.

The string will only contain lowercase letters, digits, and question marks.

• Hint: There exists an $O(kn)$ solution where $k$ is a constant. An $O(n^2)$ approach can score 100 points but will not pass the last five test cases, potentially due to large constants.

见题面 Input 部分

见题面 Output 部分