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;
const long long M = 1e9 + 7;
const long long N = 2e5 + 10;
vector<long long> fact(N), ifact(N);
long long inv(long long x) {
  long long res = 1;
  long long b = M - 2;
  while (b) {
    if (b & 1) res = (res * x) % M;
    x = (x * x) % M;
    b >>= 1;
  }
  return res;
}
bool prime[1000006];
void SieveOfEratosthenes(long long n) {
  for (long long p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
}
void init() {
  fact[0] = 1;
  for (long long i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % M;
  ifact[(long long)2e5] = inv(fact[(long long)2e5]);
  for (long long i = (long long)2e5 - 1; i >= 0; i--)
    ifact[i] = (ifact[i + 1] * (i + 1)) % M;
}
long long ncr(long long n, long long r) {
  if (r > n) return 0;
  long long res = fact[n];
  res = (res * ifact[r]) % M;
  res = (res * ifact[n - r]) % M;
  return res;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long lowbit(long long x) {
  for (long long i = 0;; i++) {
    if (x & (1 << i)) return 1 << i;
  }
}
string decimal_to_binary(long long n) {
  long long t = 0;
  long long tt = n;
  while (tt > 0) {
    t++;
    tt /= 2;
  }
  bitset<32> s = bitset<32>(n);
  string str = "";
  for (long long i = 0; i < s.size(); i++) {
    str += s[i] + '0';
  }
  reverse(str.begin(), str.end());
  return str;
}
bool checkPrime(long long x) {
  if (x == 1) {
    return false;
  }
  if (x <= 3) {
    return true;
  }
  long long t = 2;
  if (x % 2 == 0) {
    return false;
  }
  t = 3;
  for (t; t <= sqrt(x); t += 2) {
    if (x % t == 0) {
      return false;
    }
  }
  return true;
}
vector<long long> primeDivisor(long long x) {
  if (x <= 3) {
    vector<long long> r = {x};
    return r;
  }
  long long n = floor(sqrt(x));
  vector<long long> res;
  for (long long i = 2; i <= n; i++) {
    if (x % i == 0) {
      res.push_back(i);
    }
    while (x % i == 0) {
      x = x / i;
    }
    if (x < 2) {
      break;
    }
  }
  if (x > 2) {
    res.push_back(x);
  }
  return res;
}
void solve() {
  long long a;
  cin >> a;
  string s;
  cin >> s;
  map<long long, long long> m;
  for (long long i = 0; i < s.length(); i++) {
    long long sum = 0;
    for (long long j = i; j < s.length(); j++) {
      sum += (s[j] - '0');
      m[sum]++;
    }
  }
  if (a == 0) {
    long long val = m[0];
    long long ans = 0;
    ans += val * val;
    for (auto it : m) {
      if (it.first == 0) continue;
      ans += 2 * val * it.second;
    }
    cout << ans;
    return;
  } else {
    long long ans = 0;
    for (auto it : m) {
      if (it.first == 0) continue;
      if (a % (it.first) != 0) continue;
      long long u = a / (it.first);
      ans += (it.second) * m[u];
    }
    cout << ans;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
