题目描述

Alice 和 Bob 需要互相发送秘密消息，并讨论如何编码他们的消息：

• Alice："我们用一个非常简单的编码方式：将 'A' 编码为 $1$，'B' 编码为 $2$，依此类推，直到 'Z' 编码为 $26$。"
• Bob："这个编码太简单了，Alice。比如我发送单词 'BEAN'，编码为 25114，你可能会有多种解码方式！"
• Alice："确实有多种解码方式，比如 'BEAAD'、'YAAD'、'YAN'、'YKD' 和 'BEKD'，但你应该能找出正确的解码。而且你为什么要发送 'BEAN' 呢？"
• Bob："好吧，也许这个例子不太好，但如果给你一个长度为 $500$ 的数字串，解码方式会非常多，甚至可能有两种不同的解码方式都能组成有意义的单词。"
• Alice："到底有多少种解码方式？"
• Bob："天文数字！"

Alice 仍然不相信 Bob 的说法，因此她需要一个程序来计算给定数字串的可能解码方式数量。

输入格式

• 输入包含多组数据，每组数据为一行数字，表示一个有效的加密串（不会以 $0$ 开头）。
• 数字之间没有空格。
• 输入以单独一行 0 结束，该行不需要处理。

输出格式

对于每组输入，输出该数字串的可能解码方式数量。所有答案保证在 long 变量范围内。

样例输入

25114
1111111111
3333333333
0

样例输出

6
89
1