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;
void boost() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}
void solve() {
  int a;
  cin >> a;
  string s;
  cin >> s;
  long long n = s.size();
  long long ans = 0;
  vector<long long> arr(n);
  for (int i = 0; i < n; ++i) {
    arr[i] = int(s[i] - '0');
    arr[i] += (i - 1 >= 0 ? arr[i - 1] : 0);
  }
  set<long long> ss;
  map<long long, long long> mm;
  for (int i = 0; i < n; ++i) {
    if (a == 0 && arr[i] == 0) {
      ss.insert(0);
      mm[0]++;
    } else if (a != 0 && arr[i] != 0 && a % arr[i] == 0) {
      ss.insert(arr[i]);
      mm[arr[i]]++;
    }
    for (int j = 0; j < i; ++j) {
      if (a == 0 && arr[i] - arr[j] == 0) {
        ss.insert(0);
        mm[0]++;
      } else if (a != 0 && (arr[i] - arr[j]) != 0 &&
                 a % (arr[i] - arr[j]) == 0) {
        ss.insert(arr[i] - arr[j]);
        mm[arr[i] - arr[j]]++;
      }
    }
  }
  if (a == 0) {
    ans = mm[0];
    ans = (ans * ((n) * (n + 1))) - (ans * ans);
    ans = max(ans, 0LL);
    cout << ans << endl;
    return;
  }
  for (auto x : ss) {
    if (x != 0 && (a % x == 0)) {
      ans += ((mm[x]) * mm[a / x]);
    }
  }
  cout << ans << endl;
  return;
}
int main() {
  boost();
  int tc = 1;
  while (tc--) solve();
  return 0;
}
