You're visiting your friend's house again, the friend with the grade-three daughter, Alice.
“Oh, good! My programmer is here!”
“Listen kid, I'm not your programmer.”
“I've got this great idea for a secret code, for passing messages to my friends. I assign ‘A’ to the number ‘1’, ‘B’ to ‘2’, and so on, with ‘Z’ to ‘26’.”
“What about punctuation, like spaces, commas, and periods? And will you separate the numbers by spaces in the code?”
“No, no punctuation. My friends don't use it anyway. So just 1..26 for A..Z. And I'll just run the numbers together.”
“Hmm. Let's say I send you the message ‘BEAN’: ‘B’ to ‘2’, ‘E’ to ‘5’, ‘A’ to ‘1’, and ‘N’ to ‘14’. So … that gives you ‘25114’. But doesn't that have a problem? It is ambiguous. You could decode that in different ways!”
“Why you would you send me a message that said ‘BEAN’? Anyway, what else could ‘25114’ decode to? Probably nothing meaningful. Let me see … ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’, or ‘BEKD’. Well, I think I'd know you meant ‘BEAN’! But really, you'd send ‘BEAN’?!”
“Okay, sure. But the ambiguity in your encoding can get really bad. Say you send a message five hundred letters long. There would be tonnes of different decodings! And with that many, you would likely find at least two different ones that would make sense.”
“How many different decodings?”
“I don't know. Jillions!”
“Okay, smartypants! Prove it. Write me a program that counts the number of possible decodings.”
“Hey, wait a minute. This is your homework assignment, isn't it?”
Alice smiles mischievously.
The input consists of multiple trials. There will be between 1 and 100 trials, inclusive. Each trial consists of a single line of digits that represents a valid encryption. (For example, no line will begin with a ‘0’.) There are no spaces between the digits. An input line of digits is between 1 and 5000 digits long, inclusive. An input line of ‘0’ terminates the input and should not be processed.
25114 1111111111 3333333333 0
For each input trial, output the number of possible decodings for the input string. All answers are guaranteed to be within the range of a long variable.
6 89 1