#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 50;

ll M;
char s[N];

bool mul(ll &x, ll y){
    ll tt = 0;
    while(y){
    	if(x > M)  return 0;
        if(y & 1)  tt += x;
        x = x + x,  y >>= 1;
        if(tt > M)  return 0;
    }
    x = tt;
    return 1;
}

bool check(ll bs){
    ll now = 0;
    for(int i = 1; s[i]; ++i){
        int bt = s[i] - '0';
        bool ok = mul(now, bs);
        now += bt;
        if(!ok || now > M)  return 0;
    }
    return 1;
}

int main(){
    scanf("%s%lld", s + 1, &M);
    int mx = 0;
    for(int i = 1; s[i]; ++i)  mx = max(mx, s[i] - '0');
    ++mx;
	if(!check(mx))  printf("0");
	else{
		ll l = mx, r = 1e18, ans;
		if(strlen(s + 1) == 1){
			if(s[1] - '0' <= M)  puts("1");
			else  puts("0");
			return 0;
		}
		while(l <= r){
			ll mid = (l + r) >> 1;
			if(check(mid))  ans = mid, l = mid + 1;
			else  r = mid - 1;
		}	
		printf("%lld", ans - mx + 1);
	}
}
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;

string t,s;

int main()
{
	cin>>n;
	cin>>t;
	while(s.size()<t.size()+3-1)
		s+="110";
	int m=s.size();
	int cnt=0,ok0=0,ok1=0;
	for(int i=0;i<3;i++)
	{
		int ok=1;
		for(int j=0;j<t.size();j++)
			ok&=t[j]==s[i+j];
		cnt+=ok;
		if(i==0)
			ok0=ok;
		if(i==1)
			ok1=ok;
	}
	ll ans=1e10-m/3+1;
	ans*=cnt;
	if(t.size()%3==0&&ok0)
		ans++;
	if(t.size()%3==2&&(ok0||ok1))
		ans++;
	printf("%lld\n",ans);
} 
