#include<fstream>
#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
    long long m;
    string x;

    cin >> x >> m;

  if(x.size() == 1){
    if(stoi(x)<=m){
      cout << 1 << endl;
    }
    else{
      cout << 0 << endl;
    }
    return 0;
  }

  int d = 0;
  for(auto t: x) d = max(int(t-'0'),d);

  long long left = d;
  long long right = m+1;


  while(right-left>1){
    long long mid = (left + right)/2;
    long long v = 0;

    for(auto c:x){
      if(v > m/mid) v = m + 1;
      else v = v*mid + (c-'0');
    }
    if(v <= m) left = mid ;
    else right = mid ;
  }

  cout << left - d << endl;

  return 0;
}
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main(void){
    int N;
    string S;

    cin >> N;
    cin >> S;

    int sum{0};

    vector<vector<int>> nums(4,vector<int>(N+1, 0));


    for(int i{0}; i<N; ++i){
        nums[0][i+1] = nums[0][i];
        nums[1][i+1] = nums[1][i];
        nums[2][i+1] = nums[2][i];
        nums[3][i+1] = nums[3][i];
        if(S.at(i)=='A'){
            ++nums[0][i+1];
        }
        else if(S.at(i)=='T'){
            ++nums[1][i+1];
        }
        else if(S.at(i)=='C'){
            ++nums[2][i+1];
        }
        else if(S.at(i)=='G'){
            ++nums[3][i+1];
        }
    }

    for(int is{0}; is<N-1; ++is){
        for(int ie{is+2}; ie<=N; ie+=2){
            int num_A = nums[0][ie] - nums[0][is];
            int num_T = nums[1][ie] - nums[1][is];
            int num_C = nums[2][ie] - nums[2][is];
            int num_G = nums[3][ie] - nums[3][is];
            if(num_A == num_T and num_C == num_G){
                ++sum;
            }
        }
    }

    cout << sum << endl;
}
