#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

typedef long long ll;

int d, len;
ll ten[30], ans;
map<ll, ll> f[30];

ll dp(ll x, ll y)
{
	if (x >= len / 2) return (y == 0) * ten[len & 1];
	if (ten[len - x] < abs(y)) return 0;
	if (f[x].count(y)) return f[x][y];
	ll out = 0;
	for (int i = -9; i <= 9; ++i)
	{
		int times = 10 - abs(i) - (i <= 0 && x == 0);
		out += times * dp(x + 1, y + i * (ten[len - 1 - x] - ten[x]));
	}
	return f[x][y] = out;
}

int main()
{
	cin >> d;
	
	ten[0] = 1;
	for (int i = 1; i <= 18; ++i) ten[i] = ten[i - 1] * 10;
	
	for (len = 2; len <= 18; ++len)
	{
		for (int i = 0; i <= 18; ++i) f[i].clear();
		ans += dp(0, d);
	}
	
	cout << ans;
	
	return 0;
}
### Prompt

In CPP, your task is to solve 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 <iostream>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

typedef long long ll;

int d, len;
ll ten[30], ans;
map<ll, ll> f[30];

ll dp(ll x, ll y)
{
	if (x >= len / 2) return (y == 0) * ten[len & 1];
	if (ten[len - x] < abs(y)) return 0;
	if (f[x].count(y)) return f[x][y];
	ll out = 0;
	for (int i = -9; i <= 9; ++i)
	{
		int times = 10 - abs(i) - (i <= 0 && x == 0);
		out += times * dp(x + 1, y + i * (ten[len - 1 - x] - ten[x]));
	}
	return f[x][y] = out;
}

int main()
{
	cin >> d;
	
	ten[0] = 1;
	for (int i = 1; i <= 18; ++i) ten[i] = ten[i - 1] * 10;
	
	for (len = 2; len <= 18; ++len)
	{
		for (int i = 0; i <= 18; ++i) f[i].clear();
		ans += dp(0, d);
	}
	
	cout << ans;
	
	return 0;
}
```