#include <bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

typedef long long LL;

const int N = 20;

LL Pow[N], ans;

void DFS(int x, LL rem, LL ret, bool first){
	if(x <= 1){
		if(x == 1) ret *= 10 - first;
		if(!rem) ans += ret;
		return;
	}

	LL del = Pow[x - 1] - 1;
	
	int l = first ? 0 : -9, r = 9;

	For(i, l, r){
		LL nxt = rem - del * i;
		if(nxt % 10 || abs(nxt) > Pow[x]) continue;
		DFS(x - 2, nxt / 10, ret * (10 - abs(i) - first), false);
	}
	
}

int main(){
	LL d;
	scanf("%lld", &d);
	
	Pow[0] = 1;
	For(i, 1, 18) Pow[i] = Pow[i - 1] * 10;
	For(i, 1, 18) DFS(i, d, 1, 1);

	printf("%lld\n", ans);
	return 0;
}
### Prompt

Please formulate 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 For(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

typedef long long LL;

const int N = 20;

LL Pow[N], ans;

void DFS(int x, LL rem, LL ret, bool first){
	if(x <= 1){
		if(x == 1) ret *= 10 - first;
		if(!rem) ans += ret;
		return;
	}

	LL del = Pow[x - 1] - 1;
	
	int l = first ? 0 : -9, r = 9;

	For(i, l, r){
		LL nxt = rem - del * i;
		if(nxt % 10 || abs(nxt) > Pow[x]) continue;
		DFS(x - 2, nxt / 10, ret * (10 - abs(i) - first), false);
	}
	
}

int main(){
	LL d;
	scanf("%lld", &d);
	
	Pow[0] = 1;
	For(i, 1, 18) Pow[i] = Pow[i - 1] * 10;
	For(i, 1, 18) DFS(i, d, 1, 1);

	printf("%lld\n", ans);
	return 0;
}
```