You have a string of decimal digits s. Let's define bij = si·sj. Find in matrix b the number of such rectangles that the sum bij for all cells (i, j) that are the elements of the rectangle equals a in each rectangle.

A rectangle in a matrix is a group of four integers (x, y, z, t) (x ≤ y, z ≤ t). The elements of the rectangle are all cells (i, j) such that x ≤ i ≤ y, z ≤ j ≤ t.

Input

The first line contains integer a (0 ≤ a ≤ 109), the second line contains a string of decimal integers s (1 ≤ |s| ≤ 4000).

Output

Print a single integer — the answer to a problem.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

10
12345


Output

6


Input

16
439873893693495623498263984765


Output

40
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool amax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool amin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) {
    os << (it != v.begin() ? ", " : "") << *it;
  }
  os << "]";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s) {
  os << "[";
  for (typename set<T>::const_iterator it = s.begin(); it != s.end(); it++) {
    os << (it != s.begin() ? ", " : "") << *it;
  }
  os << "]";
  return os;
}
template <class Key, class Val>
ostream &operator<<(ostream &os, const map<Key, Val> &m) {
  os << "{";
  for (typename map<Key, Val>::const_iterator it = m.begin(); it != m.end();
       it++) {
    os << (it != m.begin() ? ", " : "") << it->first << ":" << it->second;
  }
  os << "}";
  return os;
}
template <class T, class S>
ostream &operator<<(ostream &os, const pair<T, S> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (size_t i = 0; i < v.size(); i++) is >> v[i];
  return is;
}
template <class Target, class Source>
inline Target lexical_cast(const Source &s) {
  Target t;
  stringstream ss;
  ss << s;
  ss >> t;
  return t;
}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
const int INFI = 1 << 28;
const long long int INFL = 1LL << 60;
const double INFD = 1e+300;
const float INFF = 1e+100;
const double EPS = 1e-8;
const long long int MOD = 1000000007;
void solve();
int main() {
  cout.setf(ios::fixed);
  cout.precision(10);
  ios_base::sync_with_stdio(false);
  solve();
  return 0;
}
void solve() {
  long long a;
  cin >> a;
  string s;
  cin >> s;
  long long N = s.size();
  vector<long long> sum(N + 1);
  for (long long i = 0; i < N; i++) {
    sum[i + 1] = sum[i] + s[i] - '0';
  }
  map<long long, long long> cnt;
  int allCnt = 0;
  for (long long i = 0; i <= N; i++) {
    for (long long j = 0; j < i; j++) {
      allCnt++;
      cnt[sum[i] - sum[j]]++;
    }
  }
  long long ans = 0;
  for (long long i = 0; i <= N; i++) {
    for (long long j = 0; j < i; j++) {
      long long tmp = sum[i] - sum[j];
      if (a == 0 && tmp == 0)
        ans += allCnt;
      else if (a == 0)
        ans += cnt[0];
      else if (tmp == 0)
        continue;
      else if (a % tmp == 0) {
        ans += cnt[a / tmp];
      }
    }
  }
  cout << ans << endl;
}
