Counting Completions of Partial Regular Expressions

You are given a partial regular expression where some characters are missing and replaced by a question mark ?. In this problem we consider a restricted subset of regular expressions. The grammar is defined as follows:

• Single character: A single character, which must be a lowercase letter (a–z) or a digit (0–9).
• Unit expression: A string of exactly three characters of the form <x>-<y>. Here both <x> and <y> are single characters (a lowercase letter or a digit) and must be of the same type. Moreover, the ASCII code of <x> must be strictly less than that of <y>. For example, 3-5 and a-d are legal, while 7-b, z-3 and 8-2 are illegal.
• Expression: A nonempty sequence of one or more inner items enclosed in square brackets [ ]. An inner item can be either a single character (as defined above) or a unit expression. Nesting of square brackets is not allowed. Immediately after the right bracket, there may be an optional quantifier which is either a star (*) or a plus (+); at most one quantifier is allowed (they cannot appear together). For example, [3-5]* and [pixi-v]+ are valid.
• A valid regular expression is a concatenation of one or more components; each component is either a single character or an expression as defined above. For instance, 0x[0-9af]*, 1[3-7]2345 and 0[7-9]*1 are valid.

Now, you are given a defective regular expression where some characters are missing (denoted by ?). Count the number of possible ways to replace each ? with a character so that the resulting regular expression is valid according to the above grammar. Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The input consists of a single line containing a nonempty string which is a partial regular expression. The missing characters are denoted by ?. The string’s length is relatively small.

outputFormat

Output a single integer – the number of possible completions modulo \(10^9+7\).

sample

0x[0-9af]*

1