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

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define int long long

const int MOD = 1e9 + 7;
const int oo = 1e9;
const int N = 1e5 + 10;

int n, ans;
int pw10[20];

int solve(int pos, int rem, bool spm)   {
    if(pos == 0) return ((rem == 0) ? 1 : 0);
    if(pos == 1) return ((rem == 0) ? 10 : 0);
    int sum = 0ll;
    for(int i = -9; i <= 9; ++i)    {
        int nex = rem - 1ll * i * (pw10[pos - 1] - 1);
        if(nex % 10 == 0)   {
            if(!spm) {
                if(i >= 0) sum += solve(pos - 2, nex / 10, true) * (9 - i);
            } else sum += solve(pos - 2, nex / 10, true) * (10 - abs(i));
        }
    }
    return sum;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    pw10[0] = 1ll; FOR(i, 1, 17) pw10[i] = pw10[i - 1] * 10;
    FOR(i, 1, 18) ans += solve(i, n, false);

    cout << ans;
    return 0;
}

### Prompt

Please create a solution in cpp 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;

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define int long long

const int MOD = 1e9 + 7;
const int oo = 1e9;
const int N = 1e5 + 10;

int n, ans;
int pw10[20];

int solve(int pos, int rem, bool spm)   {
    if(pos == 0) return ((rem == 0) ? 1 : 0);
    if(pos == 1) return ((rem == 0) ? 10 : 0);
    int sum = 0ll;
    for(int i = -9; i <= 9; ++i)    {
        int nex = rem - 1ll * i * (pw10[pos - 1] - 1);
        if(nex % 10 == 0)   {
            if(!spm) {
                if(i >= 0) sum += solve(pos - 2, nex / 10, true) * (9 - i);
            } else sum += solve(pos - 2, nex / 10, true) * (10 - abs(i));
        }
    }
    return sum;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    pw10[0] = 1ll; FOR(i, 1, 17) pw10[i] = pw10[i - 1] * 10;
    FOR(i, 1, 18) ans += solve(i, n, false);

    cout << ans;
    return 0;
}

```