#include<bits/stdc++.h>
using namespace std;
const int N=30;
typedef long long ll;

int d[N],len,tmp;
ll f[N][2][2];

ll dp(int n) {
	memset(f,0,sizeof(f));
	int m=n>>1;
	f[0][0][0]=1;
	for(int i=0;i<m;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				if(f[i][j][k]) {
					for(int x=0;x<10;x++) {
						int y=x+d[i+1]+k,k1=y/10;y%=10;
						if(k1>1) continue;
						int j1=(10*j+x-y-d[n-i]);
						if(j1!=0&&j1!=1) continue;
						if(!i&&(!x||!y)) continue;
						f[i+1][j1][k1]+=f[i][j][k];
					}
				}
	if(n&1) {
		ll ret=0;
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				for(int x=0;x<10;x++) {
					if(x+d[m+1]+k==x+j*10) ret+=f[m][j][k];
				}
		return ret;
	}
	else return f[m][0][0]+f[m][1][1];
}

int main() {
	cin>>tmp;
	while(tmp) d[++len]=tmp%10,tmp/=10;
	ll ans=0;
	for(int i=len;i<=2*len;i++) ans+=dp(i);
	cout<<ans;
	return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
using namespace std;
const int N=30;
typedef long long ll;

int d[N],len,tmp;
ll f[N][2][2];

ll dp(int n) {
	memset(f,0,sizeof(f));
	int m=n>>1;
	f[0][0][0]=1;
	for(int i=0;i<m;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				if(f[i][j][k]) {
					for(int x=0;x<10;x++) {
						int y=x+d[i+1]+k,k1=y/10;y%=10;
						if(k1>1) continue;
						int j1=(10*j+x-y-d[n-i]);
						if(j1!=0&&j1!=1) continue;
						if(!i&&(!x||!y)) continue;
						f[i+1][j1][k1]+=f[i][j][k];
					}
				}
	if(n&1) {
		ll ret=0;
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				for(int x=0;x<10;x++) {
					if(x+d[m+1]+k==x+j*10) ret+=f[m][j][k];
				}
		return ret;
	}
	else return f[m][0][0]+f[m][1][1];
}

int main() {
	cin>>tmp;
	while(tmp) d[++len]=tmp%10,tmp/=10;
	ll ans=0;
	for(int i=len;i<=2*len;i++) ans+=dp(i);
	cout<<ans;
	return 0;
}

```