#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> a;
ll dp[18][18][2][2][2];

ll solve(int l, int r, int isl, int isr, int fi){
	if(l>r)
	{
		if(isl==isr){
			return 1;
		}
		else{
			return 0;
		}
	}
	
	ll &p=dp[l][r][isl][isr][fi];
	if(p!=-1){
		return p;
	}
	
	p=0;
	for(int i=fi;i<=9;i++){
		for(int j=0;j<=9;j++){
			for(int pl=0;pl<=1;pl++){
				for(int pr=0;pr<=1;pr++){
					int ri = i-isr+10*pr;
					int rj = j;
					
					int lj = j+10*isl-pl;
					int li = i;
					
					if(ri-rj == a[r] && lj-li == a[l]){
						//cout << i << " " << j << endl;
						p+=solve(l+1,r-1,pl,pr,0);
					}
				}
			}
		}
	}
	
	return p;
} 

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int d; cin >> d;
	while(d){
		a.push_back(d%10);
		d/=10;
	}
	
	int n=a.size();
	while(a.size()<2*n){
		a.push_back(0);
	}
	reverse(a.begin(),a.end());
	
	memset(dp,-1,sizeof(dp));
	ll ans=0;
	for(int i=n;i<=2*n;i++){
		ans+=solve(2*n-i,2*n-1,0,0,1);
		//cerr << ans << endl;
	}
	
	cout << ans << endl;
	return 0;
}
### Prompt

Please create a solution in cpp 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>

using namespace std;

typedef long long ll;

vector<int> a;
ll dp[18][18][2][2][2];

ll solve(int l, int r, int isl, int isr, int fi){
	if(l>r)
	{
		if(isl==isr){
			return 1;
		}
		else{
			return 0;
		}
	}
	
	ll &p=dp[l][r][isl][isr][fi];
	if(p!=-1){
		return p;
	}
	
	p=0;
	for(int i=fi;i<=9;i++){
		for(int j=0;j<=9;j++){
			for(int pl=0;pl<=1;pl++){
				for(int pr=0;pr<=1;pr++){
					int ri = i-isr+10*pr;
					int rj = j;
					
					int lj = j+10*isl-pl;
					int li = i;
					
					if(ri-rj == a[r] && lj-li == a[l]){
						//cout << i << " " << j << endl;
						p+=solve(l+1,r-1,pl,pr,0);
					}
				}
			}
		}
	}
	
	return p;
} 

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int d; cin >> d;
	while(d){
		a.push_back(d%10);
		d/=10;
	}
	
	int n=a.size();
	while(a.size()<2*n){
		a.push_back(0);
	}
	reverse(a.begin(),a.end());
	
	memset(dp,-1,sizeof(dp));
	ll ans=0;
	for(int i=n;i<=2*n;i++){
		ans+=solve(2*n-i,2*n-1,0,0,1);
		//cerr << ans << endl;
	}
	
	cout << ans << endl;
	return 0;
}
```