#include<bits/stdc++.h>

using namespace std;

#define int long long

int p[20];

int bt(int num,int pos,int rem) {
    if (pos == num / 2)
        return  rem == 0;
    int rrr = -(rem % 10);
    if (rrr < 0)  rrr += 10;
    int ans  = bt(num,pos + 1,(rem - rrr * p[num - 2 * pos - 1]) / 10) * (10 - rrr - (pos == 0));
    if (rrr > 0)
        rrr -= 10,
        ans += bt(num,pos + 1,(rem - rrr * p[num - 2 * pos - 1]) / 10) * (10 + rrr - (pos == 0));
    return  ans;
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int dif;    cin >> dif;
    int ans = 0;

    for(int i = 1 ; i <= 18 ; ++i)
        p[i] = p[i - 1] * 10 + 9,
        ans += bt(i,0,dif) * (i & 1 ? 10 : 1);

    cout << ans << endl;
}
### 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
#include<bits/stdc++.h>

using namespace std;

#define int long long

int p[20];

int bt(int num,int pos,int rem) {
    if (pos == num / 2)
        return  rem == 0;
    int rrr = -(rem % 10);
    if (rrr < 0)  rrr += 10;
    int ans  = bt(num,pos + 1,(rem - rrr * p[num - 2 * pos - 1]) / 10) * (10 - rrr - (pos == 0));
    if (rrr > 0)
        rrr -= 10,
        ans += bt(num,pos + 1,(rem - rrr * p[num - 2 * pos - 1]) / 10) * (10 + rrr - (pos == 0));
    return  ans;
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int dif;    cin >> dif;
    int ans = 0;

    for(int i = 1 ; i <= 18 ; ++i)
        p[i] = p[i - 1] * 10 + 9,
        ans += bt(i,0,dif) * (i & 1 ? 10 : 1);

    cout << ans << endl;
}
```