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 init() { return; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  init();
  long long int a;
  cin >> a;
  string s;
  cin >> s;
  int len = s.length();
  if (a == 0) {
    long long int ans = 0ll;
    int i = 0;
    vector<long long int> arr;
    while (i < len) {
      int j = i;
      while ((j < len) and (s[j] == '0')) {
        j++;
      }
      int temp = j - i;
      ans += 2ll * ((temp * (temp + 1)) / 2) * ((1ll * len * (len + 1)) / 2);
      arr.push_back(temp);
      i = j;
      while ((j < len) and (s[j] != '0')) {
        j++;
      }
      i = j;
    }
    long long int val = 0ll;
    for (auto it : arr) {
      val += (1ll * it * (it + 1)) / 2;
    }
    ans -= 1ll * val * val;
    cout << ans << endl;
    exit(0);
  }
  vector<long long int> pfsum(len + 1);
  pfsum[0] = 0ll;
  for (int i = 0; i < len; i++) {
    pfsum[i + 1] = pfsum[i] + (s[i] - '0');
  }
  vector<long long int> factors;
  if (a == 0) factors.push_back(0ll);
  for (int i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      if (i * i == a) {
        factors.push_back(i);
      } else {
        factors.push_back(i);
        factors.push_back(a / i);
      }
    }
  }
  sort(factors.begin(), factors.end());
  unordered_map<long long int, long long int> cnt;
  for (int i = 0; i <= len; i++) {
    for (auto it : factors) {
      int idx = lower_bound(pfsum.begin() + i, pfsum.end(), pfsum[i] + it) -
                pfsum.begin();
      if ((idx <= len) and (pfsum[idx] - pfsum[i] == it)) {
        pair<vector<long long int>::iterator, vector<long long int>::iterator>
            p = equal_range(pfsum.begin() + i, pfsum.end(), pfsum[i] + it);
        cnt[it] += (p.second - p.first);
      }
    }
  }
  long long int ans = 0ll;
  for (auto it : factors) {
    ans += 1ll * cnt[it] * cnt[a / it];
  }
  cout << ans << endl;
  return 0;
}
