## 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```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MOD (ll)1000000007
#define pb   push_back
#define EPS 1e-9
#define FOR(i,n)  for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a)   printf("%d\n", a)
#define all(c)  c.begin(), c.end()
#define tr(container, it)   for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b)   si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

int main(){
io;
string input;
while(1){
cin >> input;
if(input == "0")
break;
ll dp[input.size()+1];
memset(dp, 0, sizeof(dp));
//dp[i] represents number of decodings of first i characters
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i <= input.size(); i++){
int current = input[i-1]-'0';
int previous = input[i-2]-'0';
if(current)
dp[i] = dp[i-1];
int num = previous*10+current;
if(num >= 10 && num <= 26){
dp[i] += dp[i-2];
}
}
cout << dp[input.size()] << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
25114
1111111111
3333333333
0

Output

cmd
6
89
1

### #2 Code Example with Java Programming

```Code - Java Programming```

``````import java.io.*;
class alphacode{
public static int ans;
public static void main(String[] args) throws IOException{

int x=Integer.parseInt(Character.toString(s.charAt(0)));
while(x!=0){
ans=0;
int a[]=new int[s.length()+1];
for(int i=1;i<=s.length();i++){
a[i]=Integer.parseInt(Character.toString(s.charAt(i-1)));
}
//	function(a,1,a.length);

long dp[]=new long[a.length+1];
dp[0]=1;
dp[1]=1;
int n=s.length()+1;

for(int i=2;i<n;i++){
if(a[i]==0){
dp[i]=dp[i-2];
}else if(a[i]<=6){
if(a[i-1]==1 || a[i-1]==2){
dp[i]=dp[i-1]+dp[i-2];
}else{
dp[i]=dp[i-1];
}
}else{
if(a[i-1]==1 || a[i-1]==2){
dp[i]=dp[i-1]+dp[i-2];
}else{
dp[i]=dp[i-1];
}
}
//				System.out.println(a[i]+" "+dp[i]);
}

//	ans=dp[a.length-1];
System.out.println(dp[a.length-1]);
x=Integer.parseInt(Character.toString(s.charAt(0)));
}
}
public static void function(int a[],int i,int n){
if(i>=n){
ans+=1;
return;
}else{
if(a[i]==1){
if(i<n-1){
if(a[i+1]==0){
function(a,i+1,n);
}else{
function(a,i+1,n);
function(a,i+2,n);
}
}else{
function(a,i+1,n);
}

}else if(a[i]==2){
function(a,i+1,n);
function(a,i+2,n);
}else{
function(a,i+1,n);
}

}
}
}``````
Copy The Code &

Input

cmd
25114
1111111111
3333333333
0

Output

cmd
6
89
1