「WHOI-2」Regex

_JP 版は下記のリンクをクリックしてダウンロードしてください。_ 正则表达式是文本处理的一个有用的工具。 3022 年，你看到了你以前写过的一个 Python 程序，用来某插画交流网站上面下载图片。 你很感兴趣，决定试着运行一下。结果因为年代久远，里面的正则表达式损坏了。你得恢复这个正则表达式。 然而损坏的程度有点严重……

在这里我们只考虑正则表达式的一个子集。 - **单字符**，即单独的—个字符，必须为小写字母或数字。 - **单元表达式**，指的是形如 `<x>-<y>` 的三个字符组成的字符串。其中的 `<x>` 和 `<y>` 为单字符。注意：`<x>` 和 `<y>` 必须**类型相同**，即均为数字或均为小写字母。并且 `<x>` 的 ASCII 码值必须**严格小于** `<y>`。比如 `3-5`、`a-d` 是合法的，而 `7-b`、`z-3`、`8-2` 是不合法的。 - **表达式**，指的是用**中括号**括起来的**一个或多个**单元表达式或单字符，比如 `[1-2]`、`[0-9a-f]`、 `[a-chg-k]`。在这里中括号**不允许嵌套**。在右括号后面可以有星号 `*` 或加号 `+` 修饰（两者最多只能有一个，**不能同时出现**）。比如 `[3-5]*`、`[pixi-v]+`。 - 一个合法的正则表达式由**一个或多个**表达式或单字符组成。比如 `0x[0-9af]*`、`1[3-7]2345`、`0[7-9]*1`。 现在你知道这个残缺的正则表达式，其中残缺的字符用问号 `?` 表示。 你需要计算出原来的正则表达式有多少种可能。 答案可能过大，对 $1000000007$ 取模即可。

一行一个字符串，表示残缺的正则表达式。

一行一个整数，表示所求方案数取模后的结果。

??

1296

?a?

1297

a?bc??

46730

- 样例 #1： 两个问号可以任意填数字和字母，总方案数为 $36 \times 36 = 1296$； - 样例 #2：除了数字字母，还可以填括号形成 `[a]`，总方案数为 $1297$； - 样例 #3：验题人没有给出解释。 | 测试点编号 | 字符串长度范围 | 分值 | | :-----------: | :-----------: | :-----------: | | 1 | $\leq 5$ | 20 | | 2 | $\leq 7$ | 20 | | 3 | $\leq 100$ | 20 | | 4 | $\leq 1000$ | 20 | | 5 | $\leq 5000$ | 20 | | 6 | $\leq 10^5$ | 0 | | 7 | $\leq 5 \times 10^5$ | 0 | | 8 | $\leq 10^6$ | 0 | | 9 | $\leq 5 \times 10^6$ | 0 | | 10 | $\leq 10^7$ | 0 | 字符串中只会出现**小写字母、数字、问号**中的一种或几种。 - **提示**：本题存在 $O(kn)$ 的解法，其中 $k$ 为常数。 使用 $O(n^2)$ 的做法可以在本题得到 $100$ 分，但是会由于后五个测试点无法通过而显示为 Unaccepted。可能需要注意常数。