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

const int maxK = 20;

long long D, answer;
long long power[maxK];

long long count_n(int l, int r, long long d) {
    if (l < r) {
        return !d;
    }

    long long cnt = 0;
    for (int i = (d / power[r] % 10 + 10) % 10; i > -10; i -= 10) {
        if (!r && i > 0) continue;

        int k = 10 - abs(i);
        if (!r && i <= 0) k--;
        cnt += k * count_n(l - 1, r + 1, d + i * power[l] - i * power[r]);
    }
    return cnt;
}

int main() {
   // freopen("input.in", "r", stdin);
 //   freopen("output.out", "w", stdout);

    scanf("%lld", &D);

    power[0] = 1;
    for (int i = 1; i <= 18; ++i) power[i] = power[i - 1] * 10;

    for (int i = 0; i < 18; ++i) {
        answer += count_n(i, 0, D);
    }

    printf("%lld\n", answer);

    return 0;
}

### Prompt

Your task is to create 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;

const int maxK = 20;

long long D, answer;
long long power[maxK];

long long count_n(int l, int r, long long d) {
    if (l < r) {
        return !d;
    }

    long long cnt = 0;
    for (int i = (d / power[r] % 10 + 10) % 10; i > -10; i -= 10) {
        if (!r && i > 0) continue;

        int k = 10 - abs(i);
        if (!r && i <= 0) k--;
        cnt += k * count_n(l - 1, r + 1, d + i * power[l] - i * power[r]);
    }
    return cnt;
}

int main() {
   // freopen("input.in", "r", stdin);
 //   freopen("output.out", "w", stdout);

    scanf("%lld", &D);

    power[0] = 1;
    for (int i = 1; i <= 18; ++i) power[i] = power[i - 1] * 10;

    for (int i = 0; i < 18; ++i) {
        answer += count_n(i, 0, D);
    }

    printf("%lld\n", answer);

    return 0;
}

```