#include <bits/stdc++.h>
using namespace std;

#define pb push_back
using ll = long long;
using i7 = __int128;
vector <i7> v;

int cnt[30][2];

i7 p10[30];

ll dfs(int x, int n, i7 d) {
	i7 s = 0;
	for(int i = x; i < n; i ++)
		s += v[i];
	s = 9 * s;
	if(d > s || d < -s) return 0;
	if(x == n) return 1;

	ll r = 0;
	for(int i = -9; i <= 9; i ++) {
		if(x == 0)
			r += dfs(x + 1, n, d - i * v[x]) * cnt[i + 10][1];
		else
			r += dfs(x + 1, n, d - i * v[x]) * cnt[i + 10][0];
	}
	return r;
}

int main() {
	p10[0] = 1;
	for(int i = 1; i < 30; i ++)
		p10[i] = p10[i - 1] * 10;

	for(int i = 0; i < 10; i ++)
		for(int j = 0; j < 10; j ++)
			cnt[j - i + 10][0] ++;
	for(int i = 1; i < 10; i ++)
		for(int j = 0; j < 10; j ++)
			cnt[j - i + 10][1] ++;

	int _d; cin >> _d;
	i7 d = _d;

	ll ans = 0;
	for(int n = 2; n <= 20; n ++) {
		v.clear();
		for(int i = 1; i * 2 <= n; i ++)
			v.pb(p10[n - i] - p10[i - 1]);
		//for(i7 x : v) cout << int(x) << '\n';
		if(n & 1)
			ans += dfs(0, v.size(), d) * 10;
		else
			ans += dfs(0, v.size(), d);
	}
	cout << ans << '\n';
}
### 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>
using namespace std;

#define pb push_back
using ll = long long;
using i7 = __int128;
vector <i7> v;

int cnt[30][2];

i7 p10[30];

ll dfs(int x, int n, i7 d) {
	i7 s = 0;
	for(int i = x; i < n; i ++)
		s += v[i];
	s = 9 * s;
	if(d > s || d < -s) return 0;
	if(x == n) return 1;

	ll r = 0;
	for(int i = -9; i <= 9; i ++) {
		if(x == 0)
			r += dfs(x + 1, n, d - i * v[x]) * cnt[i + 10][1];
		else
			r += dfs(x + 1, n, d - i * v[x]) * cnt[i + 10][0];
	}
	return r;
}

int main() {
	p10[0] = 1;
	for(int i = 1; i < 30; i ++)
		p10[i] = p10[i - 1] * 10;

	for(int i = 0; i < 10; i ++)
		for(int j = 0; j < 10; j ++)
			cnt[j - i + 10][0] ++;
	for(int i = 1; i < 10; i ++)
		for(int j = 0; j < 10; j ++)
			cnt[j - i + 10][1] ++;

	int _d; cin >> _d;
	i7 d = _d;

	ll ans = 0;
	for(int n = 2; n <= 20; n ++) {
		v.clear();
		for(int i = 1; i * 2 <= n; i ++)
			v.pb(p10[n - i] - p10[i - 1]);
		//for(i7 x : v) cout << int(x) << '\n';
		if(n & 1)
			ans += dfs(0, v.size(), d) * 10;
		else
			ans += dfs(0, v.size(), d);
	}
	cout << ans << '\n';
}
```