#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll ten[19];
ll dfs(int k, int L, ll x) {
	if (k == L / 2) {
		if (x) return 0;
		if (L % 2) return 10;
		return 1;
	}
	ll d[2];
	if (x >= 0) {
		d[0] = x % 10;
		d[1] = d[0] - 10;
	}
	else {
		d[0] = -((-x) % 10);
		d[1] = d[0] + 10;
	}
	ll ret = 0;
	for (int i = 0; i < 2; i++) {
		if (i == 1 && abs(x) % 10 == 0) break;
		ll y = x - d[i] * (1 - ten[L - 1 - 2 * k]);
		if (y % 10) continue;
		y /= 10;
		ll add = dfs(k + 1, L, y);
		if (k == 0) add *= 9 - abs(d[i]);
		else add *= 10 - abs(d[i]);
		ret += add;
	}
	return ret;
}
int main() {
	int D;
	cin >> D;
	ten[0] = 1;
	for (int i = 1; i <= 18; i++) ten[i] = ten[i - 1] * 10;
	ll ans = 0;
	for (int L = 1; L <= 18; L++) {
		ans += dfs(0, L, D);
	}
	cout << ans << endl;
}

### Prompt

Your task is to create 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"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll ten[19];
ll dfs(int k, int L, ll x) {
	if (k == L / 2) {
		if (x) return 0;
		if (L % 2) return 10;
		return 1;
	}
	ll d[2];
	if (x >= 0) {
		d[0] = x % 10;
		d[1] = d[0] - 10;
	}
	else {
		d[0] = -((-x) % 10);
		d[1] = d[0] + 10;
	}
	ll ret = 0;
	for (int i = 0; i < 2; i++) {
		if (i == 1 && abs(x) % 10 == 0) break;
		ll y = x - d[i] * (1 - ten[L - 1 - 2 * k]);
		if (y % 10) continue;
		y /= 10;
		ll add = dfs(k + 1, L, y);
		if (k == 0) add *= 9 - abs(d[i]);
		else add *= 10 - abs(d[i]);
		ret += add;
	}
	return ret;
}
int main() {
	int D;
	cin >> D;
	ten[0] = 1;
	for (int i = 1; i <= 18; i++) ten[i] = ten[i - 1] * 10;
	ll ans = 0;
	for (int L = 1; L <= 18; L++) {
		ans += dfs(0, L, D);
	}
	cout << ans << endl;
}

```