## ACODE - Alphacode

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

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.

### Output

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.

### Example

```Input:

25114
1111111111
3333333333
0

Output:

6
89
1
```

hide comments
 aashish_a2z: 2018-12-09 21:48:22 First of all don't worry about the invalid strings.....Take care only for valid strings Take case for the string length equal to 1 too... Check for the following test cases: 1020 --> 1 1101 --> 1 110 --> 1 All the Best :) Last edit: 2018-12-09 21:48:53 Prasanna: 2018-12-02 16:47:00 Test all these combinations:(which includes all boundary cases) 25114 1111111111 3333333333 1020 1101 110 1001 1 0 nacholibre: 2018-11-19 18:46:06 919 -> 2 me_milan_11: 2018-10-07 11:00:29 finally, AC :) handle cases which contains '10' and '20' in it. That is the tricky part. Don't bother about invalid test cases. There are no such cases. Every time answer would be > 0 masterchef2209: 2018-10-05 11:44:01 i was improving my solution according to test cases and it got accepted but i still can't understand how is my ugly code correct lol andrew_belkin: 2018-09-21 10:18:09 Thank you colleagues for all the test cases! amiratou: 2018-09-19 22:10:12 Easy Peasy ! mayank_75: 2018-09-02 23:01:15 Last edit: 2018-09-02 23:05:09 san__123: 2018-09-02 10:28:06 be careful with 0's in the input like 1101, done in c++ :) starry91: 2018-08-15 18:43:34 how can 0 occur in the input as chars start from 1-26??

 Added by: Adrian Kuegel Date: 2005-07-09 Time limit: 0.5s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: ACM East Central North America Regional Programming Contest 2004