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>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
int u[100010] = {0};
int sum[100010] = {0};
char s[4010];
long long cnt(int n, int m) {
  return n * 1ll * (n + 1) * 1ll * (m + 1) * 1ll * m / 4;
}
int main() {
  int n, len, j;
  long long ans = 0;
  vector<int> v;
  scanf("%d\n", &n);
  gets(s);
  len = strlen(s);
  if (!n) {
    for (int i = 0; i < len; i++) {
      if (s[i] == '0') {
        for (j = 1; i < len && s[i] == '0'; j++, i++)
          ;
        j--;
        ans = ans + 2 * cnt(len, j) - cnt(j, j);
        for (int(t) = 0; (t) < int((v).size()); ++(t)) ans -= 2 * cnt(j, v[t]);
        v.push_back(j);
      }
    }
  } else {
    for (int(i) = 0; (i) < (len); ++(i)) sum[i + 1] = sum[i] + (s[i] - '0');
    for (int(l) = (1); (l) <= (len); ++(l))
      for (int(r) = (l); (r) <= (len); ++(r)) u[sum[r] - sum[l - 1]]++;
    for (int(i) = (1); (i) <= (sum[len]); ++(i)) {
      if (i * i > n) break;
      if (n % i == 0) {
        if (n / i <= sum[len]) {
          ans += u[n / i] * 1ll * u[i];
          if (n / i != i) ans += u[i] * 1ll * u[n / i];
        }
      }
    }
  }
  printf("%I64d\n", ans);
  return 0;
}
