题目描述

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

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

注意，只有 10 到 26 的两位数字编码是有效的，并且不允许存在前导零（除了 10 到 26 以外的任何包含零的两位数都是非法的）。

现在需要计算并返回解码该字符串的方法的总数。如果没有合法的方式解码整个字符串，则返回 $0$。

输入格式

输入是一个只包含数字的非空字符串 s。

输出格式

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

样例

12

2

226

3

06

0

提示

样例 1 解释

解释：12 可以解码为 AB（1、 2）或者 L（12）。

样例 2 解释

解释：226 可以解码为 BZ (2、 26), VF (22、 6), 或者 BBF (2、 2、 6)。

样例 3 解释

解释：06 无法映射到任何有效的字符，因为存在前导零，所以解码方法总数为 $0$。

数据范围

• 字符串 s 的长度范围在 $1$ 到 $100$ 之间。
• 字符串 s 只包含数字，并可能包含前导零。