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 MOD = 1e9 + 7;
template <typename T>
inline T BigMod(T A, T B, T M = MOD) {
  T ret = 1;
  while (B) {
    if (B & 1) ret = (ret * A) % M;
    A = (A * A) % M;
    B = B >> 1;
  }
  return ret;
}
template <typename T>
inline T EGCD(T a, T b, T &x, T &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T x1, y1;
  T d = EGCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
template <typename T>
inline T LCM(T x, T y) {
  T g = __gcd(x, y);
  return (x / g) * y;
}
template <typename T>
inline T Distance(T x1, T y1, T x2, T y2) {
  return sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)));
}
template <typename T>
inline T Area(T Ax, T Ay, T Bx, T By, T Cx, T Cy) {
  T ret = Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By);
  if (ret < 0) return ret = -ret;
  return ret;
}
bool Check(int N, int pos) { return (bool)(N & (1 << pos)); }
int Set(int N, int pos) { return (N | (1 << pos)); }
int fx[] = {-1, +0, +1, +0, +1, +1, -1, -1, +0};
int fy[] = {+0, -1, +0, +1, +1, -1, +1, -1, +0};
template <typename T>
inline T CRT(T num[], T rem[], T k) {
  T prod = 1, result = 0;
  for (T i = 0; i < k; i++) prod *= num[i];
  for (T i = 0; i < k; i++) {
    T pp = prod / num[i];
    result += rem[i] * inv(pp, num[i]) * pp;
  }
  return result % prod;
}
const int FacN = 1000000;
long long Fac[FacN + 5];
void Facgen() {
  Fac[0] = 1;
  for (int i = 1; i <= FacN; i++) Fac[i] = (Fac[i - 1] * i) % MOD;
}
template <typename T>
inline T COM(T a, T b) {
  if (a < b) return 0;
  return ((Fac[a] * BigMod((Fac[b] * Fac[a - b]) % MOD, MOD - 2, MOD)) % MOD +
          MOD) %
         MOD;
}
long long a, s[4004];
string str;
long long ara[16000000 + 10];
unordered_map<long long, long long> mp;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  cin >> a >> str;
  for (int i = 0; i < str.size(); i++) {
    int d = str[i] - '0';
    s[i + 1] = s[i] + d;
  }
  int n = str.size();
  int in = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      ara[in] = s[j] - s[i - 1];
      mp[ara[in++]]++;
    }
  }
  long long ans = 0;
  for (int i = 0; i < in; i++) {
    if (ara[i] == 0) {
      if (a == 0) ans += in;
      continue;
    }
    if (a % ara[i] == 0) {
      ans += mp[a / ara[i]];
    }
  }
  cout << ans << "\n";
}
