问题描述

给定一个字符串 s，该字符串由数字和 * 字符组成，该字符串中的数字根据给定的映射规则进行编码：

• 1 到 9 分别映射到 'A' 到 'I'
• 10 到 26 分别映射到 'J' 到 'Z'

* 可以表示从 1 到 9 的任一数字（不包括 0）。要求解码该字符串，并返回解码方法的总数。注意，解码方法可能非常多，因此结果需要对 $10^9 + 7$ 取模。

输入格式

输入为一个字符串 s，只包含数字和 * 字符。

输出格式

输出一个整数，表示解码方法的总数。

样例输入

*

样例输出

9

样例输入

1*

样例输出

18

说明

样例1解释

这一条编码消息可以表示 1 到 9 中的任意一个数字，因此可以解码成 A 到 I 中的任意一个字母，共有 9 种解码方法。

样例2解释

这一条编码消息可以表示 11、12、13、14、15、16、17、18 或 19 中的任意一条。 每种消息都可以由 2 种方法解码（例如，11 可以解码成 AA 或 K）。 因此，1* 共有 9 * 2 = 18 种解码方法。

数据范围

• 字符串 s 可能包含前导零。