#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

#define N 25
const ll INF = 1ll << 60;

int len;
int a[N], b[N], c[N], del[N];
ll res;

void Calc(int n)
{
	for (int i = 0; i < n; ++i)
	{
		del[i] = b[i] - c[i] * 10 + (i && c[i - 1]);
		if (del[i] < -9 || del[i] > 9) return;
	}
	for (int i = 0; i < n; ++i) if (del[i] + del[n - 1 - i] != 0) return;
	
	int cnt[N] = {0};
	for (int i = 0; i <= n - 1 - i; ++i) cnt[i] = 10 - abs(del[i]);
	if (del[0] <= 0) cnt[0]--;
	ll tmp = 1;
	for (int i = 0; i <= n - 1 - i; ++i) tmp = tmp * cnt[i];
	res += tmp;
}

void DFS(int k, int n)
{
	if (k == n)
	{
		Calc(n);
		return;
	}
	c[k] = 0; DFS(k + 1, n);
	if (k < n - 1) c[k] = 1, DFS(k + 1, n);
}

int main()
{
	//freopen("in.in", "r", stdin);
	//freopen("out.out", "w", stdout);

	ll D; cin >> D;
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	for (ll t = D; D ; D /= 10) b[len++] = D % 10;
	for (int i = len; i <= 18; ++i) DFS(0, i);
	cout << res << endl;
	
	
	return 0;
}

### Prompt

Develop a solution in CPP 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 <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

#define N 25
const ll INF = 1ll << 60;

int len;
int a[N], b[N], c[N], del[N];
ll res;

void Calc(int n)
{
	for (int i = 0; i < n; ++i)
	{
		del[i] = b[i] - c[i] * 10 + (i && c[i - 1]);
		if (del[i] < -9 || del[i] > 9) return;
	}
	for (int i = 0; i < n; ++i) if (del[i] + del[n - 1 - i] != 0) return;
	
	int cnt[N] = {0};
	for (int i = 0; i <= n - 1 - i; ++i) cnt[i] = 10 - abs(del[i]);
	if (del[0] <= 0) cnt[0]--;
	ll tmp = 1;
	for (int i = 0; i <= n - 1 - i; ++i) tmp = tmp * cnt[i];
	res += tmp;
}

void DFS(int k, int n)
{
	if (k == n)
	{
		Calc(n);
		return;
	}
	c[k] = 0; DFS(k + 1, n);
	if (k < n - 1) c[k] = 1, DFS(k + 1, n);
}

int main()
{
	//freopen("in.in", "r", stdin);
	//freopen("out.out", "w", stdout);

	ll D; cin >> D;
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	for (ll t = D; D ; D /= 10) b[len++] = D % 10;
	for (int i = len; i <= 18; ++i) DFS(0, i);
	cout << res << endl;
	
	
	return 0;
}

```