#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

ll D, pw10[21], res, S[21];

void f(int x, int y, ll c, ll t) {
	if (x == y) {
		if (t == 0) {
			res += c * 10;
		}
	}
	else if (x < y) {
		if (t == 0) {
			res += c;
		}
	}
	else {
		if (S[x] >= abs(t)) {
			for (int i = 0; i <= 9; ++i) {
				f(x - 1, y + 1, c*(10 - i), t - (pw10[x] - pw10[y])*i);
			}
			for (int i = 1; i <= 9; ++i) {
				f(x - 1, y + 1, c*(10 - i), t + (pw10[x] - pw10[y])*i);
			}
		}
	}
}

int main() {
	cin >> D;
	pw10[0] = 1;
	S[0] = 9;
	for (int i = 0; i < 20; ++i) {
		pw10[i + 1] = pw10[i] * 10;
		S[i + 1] = S[i] + pw10[i + 1] * 9;
	}
	for (int i = 1; i <= 20; ++i) {
		for (int j = 0; j <= 9; ++j) {
			f(i - 1, 1, 9 - j, D - (pw10[i] - 1)*j);
		}
	}
	cout << res << endl;
}
### Prompt

Create a solution in cpp for 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 mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

ll D, pw10[21], res, S[21];

void f(int x, int y, ll c, ll t) {
	if (x == y) {
		if (t == 0) {
			res += c * 10;
		}
	}
	else if (x < y) {
		if (t == 0) {
			res += c;
		}
	}
	else {
		if (S[x] >= abs(t)) {
			for (int i = 0; i <= 9; ++i) {
				f(x - 1, y + 1, c*(10 - i), t - (pw10[x] - pw10[y])*i);
			}
			for (int i = 1; i <= 9; ++i) {
				f(x - 1, y + 1, c*(10 - i), t + (pw10[x] - pw10[y])*i);
			}
		}
	}
}

int main() {
	cin >> D;
	pw10[0] = 1;
	S[0] = 9;
	for (int i = 0; i < 20; ++i) {
		pw10[i + 1] = pw10[i] * 10;
		S[i + 1] = S[i] + pw10[i + 1] * 9;
	}
	for (int i = 1; i <= 20; ++i) {
		for (int j = 0; j <= 9; ++j) {
			f(i - 1, 1, 9 - j, D - (pw10[i] - 1)*j);
		}
	}
	cout << res << endl;
}
```