//  Created by Sengxian on 2017/6/5.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  AtCoder Regular Contest 075D DFS
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll power[19];
int pool[2][100], *c1 = pool[0] + 50, *c2 = pool[1] + 50;

ll dfs(int ALL, int n, ll D) {
	if (n == 0) return D == 0;
	if (n == 1) return (D == 0) * (9 + (ALL != 1));
	ll cnt = 0, X = power[ALL - (ALL - n) / 2 - 1] - power[(ALL - n) / 2];
	int *c = n == ALL ? c1 : c2;
	for (int i = -9; i <= 9; ++i) if (c[i]) {
		ll newD = D + i * X;
		if (fabs(newD) < X)
			cnt += c[i] * dfs(ALL, n - 2, newD);
	}
	return cnt;
}

int main() {
	power[0] = 1;
	for (int i = 1; i <= 18; ++i) power[i] = power[i - 1] * 10;
	
	for (int i = 1; i <= 9; ++i)
		for (int j = 0; j <= 9; ++j)
			c1[i - j]++;
	for (int i = 0; i <= 9; ++i)
		for (int j = 0; j <= 9; ++j)
			c2[i - j]++;

	int D;
	cin >> D;
	ll ans = 0;
	for (int i = 1; i <= 18; ++i)
		ans += dfs(i, i, D);
	cout << ans << endl;

	return 0;
}

### Prompt

Your challenge is to write 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
//  Created by Sengxian on 2017/6/5.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  AtCoder Regular Contest 075D DFS
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll power[19];
int pool[2][100], *c1 = pool[0] + 50, *c2 = pool[1] + 50;

ll dfs(int ALL, int n, ll D) {
	if (n == 0) return D == 0;
	if (n == 1) return (D == 0) * (9 + (ALL != 1));
	ll cnt = 0, X = power[ALL - (ALL - n) / 2 - 1] - power[(ALL - n) / 2];
	int *c = n == ALL ? c1 : c2;
	for (int i = -9; i <= 9; ++i) if (c[i]) {
		ll newD = D + i * X;
		if (fabs(newD) < X)
			cnt += c[i] * dfs(ALL, n - 2, newD);
	}
	return cnt;
}

int main() {
	power[0] = 1;
	for (int i = 1; i <= 18; ++i) power[i] = power[i - 1] * 10;
	
	for (int i = 1; i <= 9; ++i)
		for (int j = 0; j <= 9; ++j)
			c1[i - j]++;
	for (int i = 0; i <= 9; ++i)
		for (int j = 0; j <= 9; ++j)
			c2[i - j]++;

	int D;
	cin >> D;
	ll ans = 0;
	for (int i = 1; i <= 18; ++i)
		ans += dfs(i, i, D);
	cout << ans << endl;

	return 0;
}

```