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 N = 1e5 + 5, inf = 1e18, mod = 1000000007;
const double PI = 3.1415926536;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
long long fact(long long n) {
  n = abs(n);
  long long t = 0;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      t++;
      if (n / (n / i) != n / i) t++;
    }
  }
  return t;
}
inline long long getPow(long long a, long long b) {
  long long res = 1ll, tp = a;
  while (b) {
    if (b & 1ll) {
      res *= tp;
    }
    tp *= tp;
    tp %= mod;
    res %= mod;
    b >>= 1ll;
  }
  return res;
}
long long vec_mult(const pair<long long, long long>& t1,
                   const pair<long long, long long>& t2,
                   const pair<long long, long long>& t3) {
  const long long &x1 = t1.first, y1 = t1.second;
  const long long &x2 = t2.first, y2 = t2.second;
  const long long &x3 = t3.first, y3 = t3.second;
  return abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
}
void ok() {
  cout << "YES" << endl;
  exit(0);
}
void no() {
  cout << "NO" << endl;
  exit(0);
}
inline long long nxt() {
  long long x;
  cin >> x;
  return x;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  long long n = nxt();
  string s;
  cin >> s;
  int len = s.size();
  vector<long long> pref(len + 1);
  s = '#' + s;
  multiset<long long> st;
  for (int i = 1; i <= len; i++) {
    pref[i] = pref[i - 1] + (s[i] - '0');
    st.insert(pref[i]);
  }
  auto get = [&](long long d) {
    long long ans = 0;
    for (int i = 0; i < len; i++) {
      long long need = pref[i] + d;
      ans += st.count(need);
    }
    return ans;
  };
  long long ans = 0;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      long long t1 = get(i);
      long long t2 = get(n / i);
      if (i != n / i)
        ans += 2ll * t1 * t2;
      else
        ans += t1 * t2;
    }
  }
  if (n == 0) {
    long long zero = 0;
    for (int i = 1; i <= len; i++) {
      for (int j = 1; j <= i; j++) {
        if (pref[i] == pref[j - 1]) zero++;
      }
    }
    for (int i = 1; i <= len; i++) {
      for (int j = 1; j <= i; j++) {
        if (pref[i] == pref[j - 1]) {
          ans += len * (len + 1ll) / 2ll;
        } else {
          ans += zero;
        }
      }
    }
  }
  cout << ans;
  return 0;
}
