{"raw_statement":[{"iden":"background","content":" _JP 版は下記のリンクをクリックしてダウンロードしてください。_ \n\n正则表达式是文本处理的一个有用的工具。\n\n3022 年，你看到了你以前写过的一个 Python 程序，用来某插画交流网站上面下载图片。\n\n你很感兴趣，决定试着运行一下。结果因为年代久远，里面的正则表达式损坏了。你得恢复这个正则表达式。\n\n然而损坏的程度有点严重……"},{"iden":"statement","content":"在这里我们只考虑正则表达式的一个子集。\n\n- **单字符**，即单独的—个字符，必须为小写字母或数字。\n\n- **单元表达式**，指的是形如 `<x>-<y>` 的三个字符组成的字符串。其中的 `<x>` 和 `<y>` 为单字符。注意：`<x>` 和 `<y>` 必须**类型相同**，即均为数字或均为小写字母。并且 `<x>` 的 ASCII 码值必须**严格小于** `<y>`。比如 `3-5`、`a-d` 是合法的，而 `7-b`、`z-3`、`8-2` 是不合法的。\n\n- **表达式**，指的是用**中括号**括起来的**一个或多个**单元表达式或单字符，比如 `[1-2]`、`[0-9a-f]`、\n`[a-chg-k]`。在这里中括号**不允许嵌套**。在右括号后面可以有星号 `*` 或加号 `+` 修饰（两者最多只能有一个，**不能同时出现**）。比如 `[3-5]*`、`[pixi-v]+`。\n\n- 一个合法的正则表达式由**一个或多个**表达式或单字符组成。比如 `0x[0-9af]*`、`1[3-7]2345`、`0[7-9]*1`。\n\n\n现在你知道这个残缺的正则表达式，其中残缺的字符用问号 `?` 表示。\n\n你需要计算出原来的正则表达式有多少种可能。\n答案可能过大，对 $1000000007$ 取模即可。\n\n"},{"iden":"input","content":"一行一个字符串，表示残缺的正则表达式。"},{"iden":"output","content":"一行一个整数，表示所求方案数取模后的结果。"},{"iden":"note","content":"- 样例 #1： 两个问号可以任意填数字和字母，总方案数为 $36 \\times 36 = 1296$；\n- 样例 #2：除了数字字母，还可以填括号形成 `[a]`，总方案数为 $1297$；\n- 样例 #3：验题人没有给出解释。\n\n| 测试点编号 | 字符串长度范围 | 分值 |\n| :-----------: | :-----------: | :-----------: |\n| 1 | $\\leq 5$ | 20 |\n| 2 | $\\leq 7$ | 20 |\n| 3 | $\\leq 100$ | 20 |\n| 4 | $\\leq 1000$  | 20 |\n| 5 | $\\leq 5000$  | 20 |\n| 6 | $\\leq 10^5$ | 0 |\n| 7 | $\\leq 5 \\times 10^5$ | 0 |\n| 8 | $\\leq 10^6$ | 0 |\n| 9 | $\\leq 5 \\times 10^6$ | 0 |\n| 10 | $\\leq 10^7$ | 0 |\n\n字符串中只会出现**小写字母、数字、问号**中的一种或几种。\n\n- **提示**：本题存在 $O(kn)$ 的解法，其中 $k$ 为常数。\n\n使用 $O(n^2)$ 的做法可以在本题得到 $100$ 分，但是会由于后五个测试点无法通过而显示为 Unaccepted。可能需要注意常数。"}],"translated_statement":null,"sample_group":[["??","1296"],["?a?","1297"],["a?bc??","46730"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}