#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele long long
using namespace std;
ele D,ans,now,pw10[20];
inline ele _abs(ele x){
	return (x<0)?-x:x;
}
void dfs(ele i,ele j,ele D){
	if (i<=j){
		if (!D)
			if ((i+j)&1) ans+=now;
			else ans+=now*10;
		return;
	}
	ele tmp=pw10[i]-pw10[j];
	ele t1=D/tmp*tmp,t2;
	if (t1<D) t2=t1+tmp; else t2=t1-tmp;
	ele m=10-_abs(t1/tmp);
	if (t1>=0 && !j) --m;
	if (m>0){
		now*=m;
		dfs(i-1,j+1,D-t1);
		now/=m;
	}
	m=10-_abs(t2/tmp);
	if (t2>=0 && !j) --m;
	if (m>0){
		now*=m;
		dfs(i-1,j+1,D-t2);
		now/=m;
	}
}
int main(){
	scanf("%lld",&D);
	ans=0;
	pw10[0]=1;
	for (int i=1; i<=17; ++i) pw10[i]=pw10[i-1]*10;
	for (int i=1; i<=17; ++i) now=1,dfs(i,0,D);
	printf("%lld\n",ans);
	return 0;
}
### Prompt

In Cpp, your task is to solve 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 <cstdio>
#include <cstring>
#include <algorithm>
#define ele long long
using namespace std;
ele D,ans,now,pw10[20];
inline ele _abs(ele x){
	return (x<0)?-x:x;
}
void dfs(ele i,ele j,ele D){
	if (i<=j){
		if (!D)
			if ((i+j)&1) ans+=now;
			else ans+=now*10;
		return;
	}
	ele tmp=pw10[i]-pw10[j];
	ele t1=D/tmp*tmp,t2;
	if (t1<D) t2=t1+tmp; else t2=t1-tmp;
	ele m=10-_abs(t1/tmp);
	if (t1>=0 && !j) --m;
	if (m>0){
		now*=m;
		dfs(i-1,j+1,D-t1);
		now/=m;
	}
	m=10-_abs(t2/tmp);
	if (t2>=0 && !j) --m;
	if (m>0){
		now*=m;
		dfs(i-1,j+1,D-t2);
		now/=m;
	}
}
int main(){
	scanf("%lld",&D);
	ans=0;
	pw10[0]=1;
	for (int i=1; i<=17; ++i) pw10[i]=pw10[i-1]*10;
	for (int i=1; i<=17; ++i) now=1,dfs(i,0,D);
	printf("%lld\n",ans);
	return 0;
}
```