题目内容

一条只包含大写英文字母 $A$ 到 $Z$ 的消息按照以下规则进行了编码：

$1 \rightarrow A$

$2 \rightarrow B$

$\ldots$

$25 \rightarrow Y$

$26 \rightarrow Z$

由于某些编码可能包含在其他编码中，因此一个数字字符串可能存在多种不同的解码方式。

例如，字符串 $11106$ 可以有以下两种解码方式：

• 按照 $1,1,10,6$ 进行划分，可以解码为 $AAJF$。
• 按照 $11,10,6$ 进行划分，可以解码为 $KJF$。

需要注意的是，编码不能包含前导零。例如，$06$ 不是一个合法编码，只有 $6$ 才是合法编码。

给定一个只包含数字的非空字符串 $s$，请计算该字符串共有多少种不同的解码方式。

如果字符串无法被完整解码，则输出 $0$。

题目保证答案可以使用有符号 $32$ 位整数表示。

输入描述

输入一行字符串 $s$，表示需要解码的数字字符串。

约束

$1 \le |s| \le 100$

字符串 $s$ 仅由数字 $0$ 到 $9$ 组成。

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

输出描述

输出一个整数，表示字符串 $s$ 的不同解码方式总数。

如果不存在合法的解码方式，则输出 $0$。

样例1

输入

12

输出

2

说明

字符串 $12$ 有两种不同的解码方式。

按照 $1,2$ 进行划分，可以解码为 $AB$。

按照 $12$ 进行划分，可以解码为 $L$。

因此共有 $2$ 种解码方式。

样例2

输入

226

输出

3

说明

字符串 $226$ 有以下 $3$ 种解码方式：

按照 $2,26$ 进行划分，可以解码为 $BZ$。

按照 $22,6$ 进行划分，可以解码为 $VF$。

按照 $2,2,6$ 进行划分，可以解码为 $BBF$。

因此共有 $3$ 种解码方式。

样例3

输入

06

输出

0

说明

字符串 $06$ 不能作为一个整体进行解码，因为 $06$ 含有前导零。

同时，第一个字符 $0$ 也不能单独对应任何字母。

因此字符串 $06$ 不存在合法的解码方式，输出 $0$。