#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
 
ll dfs(ll d, ll t,int first){
  if(t==0) return (d==0);
  ll res=0;
  int v=(d%10+10)%10;
  res+=(10-v-first)*dfs((d-t*v)/10,t/100,0);
  if(t) res+=(v-first)*dfs((d+(10-v)*t)/10,t/100,0);
  return res;
}
 
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
  ll D; cin>>D;
  if(D%9){
    cout<<0<<endl;
    return 0;
  }
  D/=9;
  int ans=0;
  ll p10=1;
  for(int i=1;i<=18;i++){
    p10*=10;
    ans+=(i%2?10:1)*dfs(D,p10/10/9,1);
  }
  cout<<ans<<endl;
  return 0;
}
### 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;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
 
ll dfs(ll d, ll t,int first){
  if(t==0) return (d==0);
  ll res=0;
  int v=(d%10+10)%10;
  res+=(10-v-first)*dfs((d-t*v)/10,t/100,0);
  if(t) res+=(v-first)*dfs((d+(10-v)*t)/10,t/100,0);
  return res;
}
 
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
 
  ll D; cin>>D;
  if(D%9){
    cout<<0<<endl;
    return 0;
  }
  D/=9;
  int ans=0;
  ll p10=1;
  for(int i=1;i<=18;i++){
    p10*=10;
    ans+=(i%2?10:1)*dfs(D,p10/10/9,1);
  }
  cout<<ans<<endl;
  return 0;
}
```