题目背景

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：验题人没有给出解释。

字符串中只会出现小写字母、数字、问号中的一种或几种。

• 提示：本题存在 $O(kn)$ 的解法，其中 $k$ 为常数。

使用 $O(n^2)$ 的做法可以在本题得到 $100$ 分，但是会由于后五个测试点无法通过而显示为 Unaccepted。可能需要注意常数。