#include<iostream>
#include<array>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}

ll Kth_root(ll x,int k){
    if(x==1) return 1;
    if(k>64) return 1;
    ll l=0,r=numeric_limits<ll>::max();
    while(r-l>1){
        ll mid=(l+r)/(ll)2;
        ll d=mid;
        bool larger=false;
        rep(i,k-1){
            if(d>x/mid+(ll)1){
                larger=true;
                break;
            }
            d*=mid;
        }
        if(d>x) larger=true;
        if(larger) r=mid;
        else l=mid;
    }
    return l;
}


string x;
ll m;

void solve(){
    cin >> x;
    cin >> m;
    int n=x.length();
    int ans=0;
    int l=0;
    rep(i,n){
        chmax(l,x[i]-'0');
    }
    if(n==1){
        if(x[0]-'0'<=m) cout << 1 << endl;
        else cout << 0 << endl;
        return;
    }
    if(n==2){
        ll a=x[0]-'0',b=x[1]-'0';
        cout << max(0ll,(m-b)/a-l) << endl;
        return;
    }
    ll L=l,R=mod;
    while(R-L>1){
        ll mid=(L+R)/2;
        ll A=0,D=1;
        rep(i,n){
            A+=D*(x[n-1-i]-'0');
            if(i<n-1) D*=mid;
            if(D>m || D<0) break;
        }
        if(D>m || D<0 || A>m) R=mid;
        else L=mid;
    }
    cout << L-l << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(50);
    solve();
}
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
  int n;
  ll x;
  cin >> n >> x;
  vector<ll> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  unordered_map<ll, ll> v;
  v[x] = 1;
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    unordered_map<ll, ll> nv;
    for (auto [c, f] : v) {
      if (i + 1 < n) {
        ll rem = c % a[i + 1];
        nv[c - rem] += f;
        if (rem > 0)
          nv[c + a[i + 1] - rem] += f;
      } else {
        if (c % a[i] == 0)
          nv[0] += f;
      }
    }
    v = move(nv);
  }
  cout << v[0];
}