#include <bits/stdc++.h>

using namespace std;
using ll=long long ;

int D;

int res = 0;
ll pw[19];
int digit[19];

void dfs(int high, int low, ll dif, ll way, bool carry) {
    if (high < low) {
        if (dif == D) res += way;
    } else if(high == low) {
        dfs(high-1, low+1, dif, way*10, 0);
    } else {
        int d = digit[low] + carry; carry = 0;
        if (d == 10) d = 0, carry = 1;
        dfs(high-1, low+1, dif + (pw[low] - pw[high])*d, way*(10-d-(low==0 && d==0)), carry);
        if (d > 0) {
            dfs(high-1, low+1, dif + (pw[low] - pw[high])*(d-10), way*(d - (low==0)), 1);
        }
    }
}

void solve() {
    cin >> D;
    pw[0] = 1;
    for (int i = 1; i <= 18; i++) {
        pw[i] = 10*pw[i-1];
    }
    ll x = D;
    for (int i = 0; i <= 18; i++) {
        digit[i] = x%10;
        x/=10;
    }
    for (int len = 1; len <= 18; len++) {
        dfs(len-1, 0, 0, 1, 0);
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
using ll=long long ;

int D;

int res = 0;
ll pw[19];
int digit[19];

void dfs(int high, int low, ll dif, ll way, bool carry) {
    if (high < low) {
        if (dif == D) res += way;
    } else if(high == low) {
        dfs(high-1, low+1, dif, way*10, 0);
    } else {
        int d = digit[low] + carry; carry = 0;
        if (d == 10) d = 0, carry = 1;
        dfs(high-1, low+1, dif + (pw[low] - pw[high])*d, way*(10-d-(low==0 && d==0)), carry);
        if (d > 0) {
            dfs(high-1, low+1, dif + (pw[low] - pw[high])*(d-10), way*(d - (low==0)), 1);
        }
    }
}

void solve() {
    cin >> D;
    pw[0] = 1;
    for (int i = 1; i <= 18; i++) {
        pw[i] = 10*pw[i-1];
    }
    ll x = D;
    for (int i = 0; i <= 18; i++) {
        digit[i] = x%10;
        x/=10;
    }
    for (int len = 1; len <= 18; len++) {
        dfs(len-1, 0, 0, 1, 0);
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}

```