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 double PI = 3.14159265358979323846;
const double SQRT2 = 1.41421356237;
const double EPS = 1e-9;
const float SQRT2F = (float)SQRT2;
const int INF = 1e9;
const long long INF64 = 1e18;
template <class T>
T sqr(const T &x) {
  return x * x;
}
template <class T>
T min(const T &a, const T &b, const T &c) {
  return min(min(a, b), c);
}
template <class T>
T max(const T &a, const T &b, const T &c) {
  return max(max(a, b), c);
}
inline void yesno(bool y) { cout << (y ? "YES\n" : "NO\n"); }
inline void yes_stop(bool y) {
  if (y) {
    yesno(1);
    exit(0);
  }
}
inline void no_stop(bool y) {
  if (!y) {
    yesno(0);
    exit(0);
  }
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int sgn(int x) { return (x > 0) - (x < 0); }
long long a, ans, cnt[100500];
int l, ps[5000];
short n[5000];
inline long long get(int l, int r) { return (l ? ps[r] - ps[l - 1] : ps[r]); }
int main() {
  ios_base::sync_with_stdio(0);
  char c;
  cin >> a;
  while (cin >> c) {
    if (c == '.') break;
    n[l++] = c - '0';
  }
  if (a > l * l * 100) {
    cout << "0\n";
    return 0;
  }
  ps[0] = n[0];
  for (int i = 1; i < l; ++i) {
    ps[i] = ps[i - 1] + n[i];
  }
  for (int i = 0; i < l; ++i) {
    for (int j = i; j < l; ++j) {
      int s = get(i, j);
      ++cnt[s];
    }
  }
  if (a == 0) {
    ans = cnt[0] * l * (l + 1) - cnt[0] * cnt[0];
    cout << ans << "\n";
    return 0;
  }
  for (int i1 = 0; i1 < l; ++i1) {
    for (int j1 = i1; j1 < l; ++j1) {
      int s1 = get(i1, j1);
      if (!s1 || s1 > a || a % s1) continue;
      int s2 = a / s1;
      if (s2 >= 100500) continue;
      ans += cnt[s2];
    }
  }
  cout << ans << endl;
  return 0;
}
