#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline int read(){
	int sum = 0, t = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') t = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ sum = sum * 10 + ch - '0'; ch = getchar(); }
	return sum * t;
}

int D;
ll pw[20], sum[20], ans;

vector<ll>A;

ll dfs(int x, ll val){
	if(x == A.size()) return !val;
	if(val < -sum[x] * 9 || val > sum[x] * 9) return 0;
	ll res = 0;
	for(int i = 0; i <= 9; i++){
		int t = 9 - i + (x != 0);
		res += dfs(x + 1, val - i * A[x]) * t;
	}
	for(int i = 1; i <= 9; i++){
		int t = 10 - i;
		res += dfs(x + 1, val + i * A[x]) * t;
	}
	return res;
}

int main(){
	pw[0] = 1;
	for(int i = 1; i < 19; i++)  pw[i] = pw[i - 1] * 10;
	D = read();
	for(int i = 2; i <= 18; i++){
		A.clear();
		for(int j = i - 1, k = 0; j > k; j--, k++)
			A.push_back(pw[j] - pw[k]);
		sum[A.size()] = 0;
		for(int j = A.size() - 1; ~j ; j--)
			sum[j] = sum[j + 1] + A[j];
		ll res = dfs(0, D);
		if(i & 1) res *= 10;
		ans += res;
	}
	printf("%lld\n", ans);
}

### 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<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
inline int read(){
	int sum = 0, t = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') t = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ sum = sum * 10 + ch - '0'; ch = getchar(); }
	return sum * t;
}

int D;
ll pw[20], sum[20], ans;

vector<ll>A;

ll dfs(int x, ll val){
	if(x == A.size()) return !val;
	if(val < -sum[x] * 9 || val > sum[x] * 9) return 0;
	ll res = 0;
	for(int i = 0; i <= 9; i++){
		int t = 9 - i + (x != 0);
		res += dfs(x + 1, val - i * A[x]) * t;
	}
	for(int i = 1; i <= 9; i++){
		int t = 10 - i;
		res += dfs(x + 1, val + i * A[x]) * t;
	}
	return res;
}

int main(){
	pw[0] = 1;
	for(int i = 1; i < 19; i++)  pw[i] = pw[i - 1] * 10;
	D = read();
	for(int i = 2; i <= 18; i++){
		A.clear();
		for(int j = i - 1, k = 0; j > k; j--, k++)
			A.push_back(pw[j] - pw[k]);
		sum[A.size()] = 0;
		for(int j = A.size() - 1; ~j ; j--)
			sum[j] = sum[j + 1] + A[j];
		ll res = dfs(0, D);
		if(i & 1) res *= 10;
		ans += res;
	}
	printf("%lld\n", ans);
}

```