Background

JP version: please click the link below to download.

Regular expressions are a useful tool for text processing.

In the year 3022, you found a Python program you wrote before, used to download images from an illustration sharing website.

You were very interested and decided to try running it. However, since it was written a long time ago, the regular expression inside was broken. You need to restore this regular expression.

Unfortunately, the damage is quite serious…

Problem Description

Here we only consider a subset of regular expressions.

• Single character: a single character by itself, which must be a lowercase letter or a digit.

• Unit expression: a string of three characters in the form <x>-<y>. Here <x> and <y> are single characters. Note that <x> and <y> must be of the same type, i.e., both digits or both lowercase letters. Also, the ASCII code 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: one or more unit expressions or single characters enclosed in square brackets, such as [1-2], [0-9a-f], and [a-chg-k]. Square brackets cannot be nested here. After the right bracket, there may be a * or + modifier (at most one of them, and they cannot appear at the same time), such as [3-5]* and [pixi-v]+.

• A valid regular expression consists of one or more expressions or single characters, such as 0x[0-9af]*, 1[3-7]2345, and 0[7-9]*1.

Now you are given this incomplete regular expression, where missing characters are represented by question marks ?.

You need to compute how many possible original regular expressions there are.
The answer may be very large; output it modulo $1000000007$.

Input Format

One line containing a string, representing the incomplete regular expression.

Output Format

One line containing an integer, representing the required number of ways modulo $1000000007$.

??

1296

?a?

1297

a?bc??

46730

Hint

• Sample #1: the two question marks can be filled with any digits or letters, so the total number of ways is $36 \times 36 = 1296$.
• Sample #2: besides digits and letters, you can also fill in brackets to form [a], so the total number of ways is $1297$.
• Sample #3: the setter did not provide an explanation.

The string will contain only one or more of lowercase letters, digits, and question marks.

• Hint: This problem has an $O(kn)$ solution, where $k$ is a constant.

An $O(n^2)$ approach can get $100$ points on this problem, but it will be shown as Unaccepted because it cannot pass the last five test points. You may need to pay attention to constant factors.

Translated by ChatGPT 5