#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

i64 ten[25];



i64 dfs(i64 r,i64 l,i64 d){
  if(l >= r){
    return (d == 0) * (l == r ? 10 : 1);
  }
  i64 to = (ten[r] - ten[l]) / ten[l] / 9;
  int now = (d % 10 + 10) % 10;
  return dfs(r - 1,l + 1,(d - now * to) / 10) * (10 - now - (l == 1)) + 
    (now == 0 ? 0 : (dfs(r - 1,l + 1,(d + (10 - now) * to) / 10) * (now - (l == 1))));
}

int main(){
  ten[1] = 1;
  for(int i = 2;i < 25;i++) ten[i] = ten[i - 1] * 10;
  i64 D;
  cin >> D;
  if(D % 9 != 0){
    cout << 0 << endl;
    return 0;
  }
  i64 ans = 0;
  for(int i = 2;i <= 18;i++){
    ans += dfs(i,1,D / 9);
  }
  cout << ans << endl;
}

### Prompt

Generate 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;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

i64 ten[25];



i64 dfs(i64 r,i64 l,i64 d){
  if(l >= r){
    return (d == 0) * (l == r ? 10 : 1);
  }
  i64 to = (ten[r] - ten[l]) / ten[l] / 9;
  int now = (d % 10 + 10) % 10;
  return dfs(r - 1,l + 1,(d - now * to) / 10) * (10 - now - (l == 1)) + 
    (now == 0 ? 0 : (dfs(r - 1,l + 1,(d + (10 - now) * to) / 10) * (now - (l == 1))));
}

int main(){
  ten[1] = 1;
  for(int i = 2;i < 25;i++) ten[i] = ten[i - 1] * 10;
  i64 D;
  cin >> D;
  if(D % 9 != 0){
    cout << 0 << endl;
    return 0;
  }
  i64 ans = 0;
  for(int i = 2;i <= 18;i++){
    ans += dfs(i,1,D / 9);
  }
  cout << ans << endl;
}

```