#include<stdio.h>
#include<iostream>
using namespace std;
struct hi{int a[10005],w;}a,t1,ans,C[52][52],fang[52],fang1[52];
int m;
string s;
hi chan(int x)
{
    hi a;
    a.w=0;
    while(x)
        a.a[++a.w]=x%10000,
        x/=10000;
    return a;
}
void print(hi a)
{
	if(a.w==0) {printf("0\n");return;}
	printf("%d",a.a[a.w]);
	for(int i=a.w-1;i>=1;i--)
	{
		if(a.a[i]>=1000) printf("%d",a.a[i]);
		else if(a.a[i]>=100) printf("0%d",a.a[i]);
		else if(a.a[i]>=10) printf("00%d",a.a[i]);
		else if(a.a[i]>=1) printf("000%d",a.a[i]);
		else printf("0000");
	}
	printf("\n");
} 
bool cmp(hi a,hi b)
{
    if(a.w>b.w) return 0;
    if(b.w>a.w) return 1;
    for(int i=a.w;i>=1;i--)
    {
        if(a.a[i]>b.a[i]) return 0;
        if(b.a[i]>a.a[i]) return 1;
    }
    return 1;
}
hi pl(hi a,hi b)
{
    hi c;
    c.w=max(a.w,b.w);
    c.a[c.w+1]=0;
    if(a.w>b.w) for(int i=b.w+1;i<=a.w;i++) b.a[i]=0;
    if(a.w<b.w) for(int i=a.w+1;i<=b.w;i++) a.a[i]=0;
    for(int i=1;i<=c.w;i++) c.a[i]=a.a[i]+b.a[i];
    for(int i=1;i<=c.w;i++) c.a[i+1]+=c.a[i]/10000,c.a[i]%=10000;
    if(c.a[c.w+1]>0) c.w++;
    return c;
}
hi ti(hi a,int b)
{
	for(int i=a.w+1;i<=a.w+7;i++) a.a[i]=0;
    for(int i=1;i<=a.w;i++) a.a[i]*=b;
    for(int i=1;i<=a.w+5;i++) a.a[i+1]+=a.a[i]/10000,a.a[i]%=10000;
    while(a.a[a.w+1]>0) a.w++;
    return a;
}
hi times(hi a,hi b)
{
    hi c;
    c.w=a.w+b.w-1;
    for(int i=1;i<=c.w+10;i++) c.a[i]=0;
    if(a.w==0||b.w==0) {c.w=0;return c;}
    for(int i=1;i<=a.w;i++)
        for(int j=1;j<=b.w;j++)
            c.a[i+j-1]+=a.a[i]*b.a[j];
    for(int i=1;i<=c.w+9;i++) c.a[i+1]+=c.a[i]/10000,c.a[i]%=10000;
    while(c.a[c.w+1]>0) c.w++;
    return c;
}
void init()
{
    for(int i=0;i<=m;i++)
        for(int j=0;j<=m;j++) C[i][j].w=0;
    C[0][0]=chan(1);
    for(int i=1;i<=m+1;i++)
        for(int j=0;j<=i-1;j++) C[i][j]=pl(C[i-1][j-1],C[i-1][j]);
    return;
}
hi f(int b,int m)//(a+b)^m
{
    hi res;
    hi t1;
    res=chan(0);
    t1=chan(1);
    //for(int i=1;i<=10;i++) res.a[i]=0;
    for(int i=m;i>=0;i--) res=pl(res,times(times(C[m+1][m-i],fang[i]),t1)),t1=ti(t1,b);
    return res;
}
int main()
{
    scanf("%d",&m);
    init();
    cin>>s;
    int L=s.length();
    while(s[L-1]==' '||s[L-1]=='EOF') L--;
    //L--;
    a.w=(L+3)/4;
    for(int i=1;i<=a.w-1;i++)
        a.a[i]=s[(L-i*4)]*1000+s[(L-i*4)+1]*100+s[(L-i*4)+2]*10+s[(L-i*4)+3]-'0'*1111;
    if(a.w*4-L==3) a.a[a.w]=s[0]-'0';
    if(a.w*4-L==2) a.a[a.w]=s[0]*10+s[1]-'0'*11;
    if(a.w*4-L==1) a.a[a.w]=s[0]*100+s[1]*10+s[2]-'0'*111;
    if(a.w*4-L==0) a.a[a.w]=s[0]*1000+s[1]*100+s[2]*10+s[3]-'0'*1111;
    ans.w=((a.w*4+m-1)/m+3)/4;
//    printf("%d %d\n",ans.w,L);
//    print(a);
//	for(int i=0;i<=m;i++) {for(int j=0;j<=i;j++) print(C[i][j]);printf("\n");}
    for(int i=ans.w;i>=1;i--)
    {
        t1.w=0;
        for(int j=(i-1)*m+1;j<=a.w;j++) t1.a[++t1.w]=a.a[j];
        //print(t1);
        //for(int i=1;i<=m;i++) fang[i]=chan(0);
        int l=0,r=9999;
		//fang[m]=chan(0);
		fang[0]=chan(1);
        while(l<r)
		{
			fang1[m]=chan(0);
			fang1[0]=chan(1);
		    int mid=(l+r+1)/2;
		    fang1[m]=f(mid,m);
		    int t=cmp(fang1[m],t1);
	        //printf("::::::::::::::::::::::::::::::::::%d %d %d %d:",i,mid,fang1[m].w,t);
	        //print(fang1[m]);
	        if(t) l=mid;
	        else r=mid-1;
		}
        for(int k=1;k<=m;k++)
            fang1[k]=f(r,k);
        for(int k=1;k<=m;k++)
        {
        	int t2=fang1[k].w+k;
        	for(int l=t2;l>=t2-fang1[k].w;l--) fang1[k].a[l]=fang1[k].a[fang1[k].w-t2+l];
        	for(int l=1;l<=t2-fang1[k].w;l++) fang1[k].a[l]=0;
        	fang1[k].w=t2;
//           	printf("%d:",t2);
//			print(fang1[k]);
		}
        for(int k=1;k<=m;k++) fang[k]=fang1[k];
        ans.a[i]=r;
    }
    print(ans);
}

写得有点乱，主要是四位四位二分试，再用牛顿二项式定理优化。