题目描述

字母 A 到 Z 分别用整数 1 到 26 表示。给定一个仅含数字的非空字符串，求它能被解码成多少个字母串，答案对 $1000000007$ 取模。数字 0 不能单独解码。

输入格式

一行一个数字字符串 $s$。

输出格式

输出合法解码方案数对 $1000000007$ 取模的结果。

样例

226

3

数据规模与约定

$1\le |s|\le200000$。