#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

ll ans, n, cnt;
ll pos;

void dfs(ll ,ll , ll, ll);

int main(){
	cin >> n;
	if(n % 9){
		puts("0");
		return 0;
	}
	while(pos >= 0){
		pos = pos * 10 + 9, ++cnt;
		dfs(n, pos, 1, 100);
	}
	cout << ans << endl;
	return 0;
}

void dfs(ll u,ll d,ll sum, ll tmp){
	if(!d){
		if(u) return;
		if(cnt % 2 == 0) sum *= 10;
		ans += sum;
		return ;
	}
	ll tmp1 = u / d, tmp2 = u % d;
	if(tmp1 >= 10) return ;
	ll sum1 = 10 - tmp1, sum2 = 9 - tmp1;
	if(d == pos) sum1--, sum2--;
	dfs(tmp2, d / tmp * (tmp / 10), sum * sum1, tmp * 10);
	dfs(d - tmp2, d / tmp * (tmp / 10), sum * sum2, tmp * 10);
	return ;
}

### 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 <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

ll ans, n, cnt;
ll pos;

void dfs(ll ,ll , ll, ll);

int main(){
	cin >> n;
	if(n % 9){
		puts("0");
		return 0;
	}
	while(pos >= 0){
		pos = pos * 10 + 9, ++cnt;
		dfs(n, pos, 1, 100);
	}
	cout << ans << endl;
	return 0;
}

void dfs(ll u,ll d,ll sum, ll tmp){
	if(!d){
		if(u) return;
		if(cnt % 2 == 0) sum *= 10;
		ans += sum;
		return ;
	}
	ll tmp1 = u / d, tmp2 = u % d;
	if(tmp1 >= 10) return ;
	ll sum1 = 10 - tmp1, sum2 = 9 - tmp1;
	if(d == pos) sum1--, sum2--;
	dfs(tmp2, d / tmp * (tmp / 10), sum * sum1, tmp * 10);
	dfs(d - tmp2, d / tmp * (tmp / 10), sum * sum2, tmp * 10);
	return ;
}

```