ACODE - Alphacode

Alice和Bob需要向对方发送秘密信件，并正在讨论对信件进行加密的方法： Alice：“我们只使用一个非常简单的方式：我们将'A'对应密文1，'B'对应密文2，依此类推，26对应明文'Z'。” Bob：“这是一个愚蠢的加密方式，Alice。假设我发送了“BEAN”这个词，编码为25114.你可以用许多不同的方式对它进行解码！“ Alice：“当然可以，但你会得到什么样的话？除了'BEAN'，你会得到'BEAAD'，'YAAD'，'YAN'，'YKD'和'BEKD'。我想你能找出正确的解密方法。还有你为什么还要给我发“BEAN”这个词呢？“ Bob：“好吧，也许这是一个不好的例子，但我敢打赌，如果你得到一串长度为5000的字符串会有大量不同的解密方式，而且你会发现至少有两个不同且符合语法的解密方式。” Alice：“有多少种不同的解密方式？” Bob：“太多了！” 出于某种原因，Alice仍然不相信Bob的观点，因此她需要一个程序来确定使用她的代码对给定字符串有多少种解码方式。 ------------ ### 输入输出格式 #### 输入格式： 输入将包含多行。每行将由最多5000个数字的单行组成，表示有效加密（例如：没有以0开头）。数字之间不会有空格。最后一行'0'表示终止输入，不应处理。 #### 输出格式： 对于每行输入，输出输入字符串的可能解码数。所有答案都在64位正整数的范围内。

Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages: > Alice: “Let’s just use a very simple code: We’ll assign ‘A’ the code word 1, ‘B’ will be 2, and so on down to ‘Z’ being assigned 26.” > > Bob: “That’s a stupid code, Alice. Suppose I send you the word ‘BEAN’ encoded as 25114. You could decode that in many different ways!” > > Alice: “Sure you could, but what words would you get? Other than ‘BEAN’, you’d get ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ and ‘BEKD’. I think you would be able to figure out the correct decoding. And why would you send me the word ‘BEAN’ anyway?” > > Bob: “OK, maybe that’s a bad example, but I bet you that if you got a string of length 5000 there would be tons of different decodings and with that many you would find at least two different ones that would make sense.” > > Alice: “How many different decodings?” > > Bob: “Jillions!” For some reason, Alice is still unconvinced by Bob’s argument, so she requires a program that will determine how many decodings there can be for a given string using her code.

Input will consist of multiple input sets. Each set will consist of a single line of at most 5000 digits representing a valid encryption (for example, no line will begin with a 0). There will be no spaces between the digits. An input line of ‘0’ will terminate the input and should not be processed.

For each input set, output the number of possible decodings for the input string. All answers will be within the range of a 64 bit signed integer.

25114
1111111111
3333333333
0

6
89
1