‹ 上一题 下一题 ›

g6-07879. 解码方法·前导零 未做

1000 ms 256 MB 测试点 ? 6级·线性DPGESP-6前缀型假设

题目描述

一条只含数字的字符串 ,把 编码成 1~26。求把 解码成字母串的方案数,答案对 取模。

本题的数据特意包含前导零和连续零:0 不能单独解码,只能作为 10 或 20 的第二位。

输入格式

一行一个字符串 。

输出格式

一行一个整数,表示方案数。

样例

输入 1

06

输出 1

0

输入 2

226

输出 2

3

数据范围

, 只含数字。

输入
输出

            
答案