🐾 星号密码破解战

（兔猫信奥学院 · 牛局长特派任务）

故事背景

哨兵城安全局的 牛局长 带着闪电来到学院，交给 豹警官、朱迪、尼克 一段神秘电报。 电报是一串只含数字和 * 的编码，规则如下：

* 代表 任意数字 1–9。 例如，"1*" 既可能是 "11"、也可能是 "19"，而 0 不能单独映射任何字母。

牛局长下达命令：

“统计所有可能的解码方案数（因结果巨大，对 $10^9+7$ 取模）！”

闪电蹒跚着掏出笔记本，尼克与朱迪摩拳擦掌，等待你给出答案与算法。

题目描述

给定长度为 $n$ 的字符串 $s$（仅含字符 '0'–'9' 与 '*'），其中 '*' 可取 1–9 中任意数字。解码规则与表格一致，且任何数字段不能有前导 0。 请计算 所有可行解码方案总数，结果对 $M = 10^9+7$ 取模。

输入格式

s

• 仅一行，编码字符串 s。

输出格式

ans

• 解码方案数 $\bmod;10^9+7$。

样例

数据范围

提示

• 令 dp[i] 为前 i 个字符的解码方案数，可用滚动数组在 $O(n)$ 时间、$O(1)$ 额外空间求解。

• 计算子函数：

  • ways1(c) —— 单字符 c 的解码方式数；
  • ways2(a,b) —— 两字符 ab 的解码方式数（考虑 *）。