#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL D,P[21],Res;
int main(){
    scanf("%lld",&D);
    P[0LL]=1LL;
    for(LL I=1LL;I<=18LL;I++) P[I]=P[I-1LL]*10LL;
    for(LL Len=2LL;Len<=18LL;Len++){
    	LL K=Len/2LL;
    	for(LL S=0LL;S<(1LL<<K);++S){
    		LL Ways=((Len&1LL)?10LL:1LL),Zan=D;
    		for(LL I=0LL;I<K;I++){
    			LL Dig=(Zan%10LL+10LL)%10LL;
				if(S&(1LL<<I)){
    				LL DigitWays=Dig;
					if(I==0LL) --DigitWays;
					if(DigitWays<0LL){Ways=0LL;  break;}
					Ways*=DigitWays;
					Zan-=(10LL-Dig)*P[Len-2LL*I-1LL];
					Zan+=(10LL-Dig);
				}
				else{
					LL DigitWays=10LL-Dig;
					if(I==0LL) --DigitWays;
					Ways*=DigitWays;
					Zan+=Dig*P[Len-2LL*I-1LL];
					Zan-=Dig;
				}
				Zan/=10LL;
				if(Ways==0LL) break;
			}
			if(Zan==0LL) Res+=Ways;
		}
	}
	printf("%d",Res);
	return 0;
}
### Prompt

Your task is to create a Cpp solution to the following problem:

For a positive integer n, we denote the integer obtained by reversing the decimal notation of n (without leading zeroes) by rev(n). For example, rev(123) = 321 and rev(4000) = 4.

You are given a positive integer D. How many positive integers N satisfy rev(N) = N + D?

Constraints

* D is an integer.
* 1 ≤ D < 10^9

Input

Input is given from Standard Input in the following format:


D


Output

Print the number of the positive integers N such that rev(N) = N + D.

Examples

Input

63


Output

2


Input

75


Output

0


Input

864197532


Output

1920

### Response

```cpp
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL D,P[21],Res;
int main(){
    scanf("%lld",&D);
    P[0LL]=1LL;
    for(LL I=1LL;I<=18LL;I++) P[I]=P[I-1LL]*10LL;
    for(LL Len=2LL;Len<=18LL;Len++){
    	LL K=Len/2LL;
    	for(LL S=0LL;S<(1LL<<K);++S){
    		LL Ways=((Len&1LL)?10LL:1LL),Zan=D;
    		for(LL I=0LL;I<K;I++){
    			LL Dig=(Zan%10LL+10LL)%10LL;
				if(S&(1LL<<I)){
    				LL DigitWays=Dig;
					if(I==0LL) --DigitWays;
					if(DigitWays<0LL){Ways=0LL;  break;}
					Ways*=DigitWays;
					Zan-=(10LL-Dig)*P[Len-2LL*I-1LL];
					Zan+=(10LL-Dig);
				}
				else{
					LL DigitWays=10LL-Dig;
					if(I==0LL) --DigitWays;
					Ways*=DigitWays;
					Zan+=Dig*P[Len-2LL*I-1LL];
					Zan-=Dig;
				}
				Zan/=10LL;
				if(Ways==0LL) break;
			}
			if(Zan==0LL) Res+=Ways;
		}
	}
	printf("%d",Res);
	return 0;
}
```