#include<stdio.h>
int L,a,n,sol[110],k[100],
N[110][110][110],A[110][110][110],AT[110][110],NT[110][110],LC,x,CC,mic(int *u,int *v);
void read(),solve(),init1(int *u),printez(int *u),
atrib(int *u,int *v),adun(int *u,int *v),scad(int *u,int *v);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	char ks[100];
	int j;
	freopen("pavare2.in","r",stdin);
	freopen("pavare2.out","w",stdout);
	scanf("%d%d%d",&L,&a,&n);
	scanf("%s",ks);
	for(x=0;ks[x];++x);
	k[0]=x;
	for(j=x;j>=1;j--)k[j]=ks[x-j]-'0';
}
void solve()
{
	for(LC=1;LC<=L;LC++)
	{
		for(x=1;x<=a;x++)
		{
			if(x>LC);
			else
			if(x==LC)init1(A[LC][x]);
			else
			if(x==1)atrib(A[LC][x],NT[LC-1]);
			else
			atrib(A[LC][x],A[LC-1][x-1]);
			adun(AT[LC],A[LC][x]);
		}
		for(x=1;x<=n;x++)
		{
			if(x>LC);
			else
			if(x==LC)init1(N[LC][x]);
			else
			if(x==1)atrib(N[LC][x],AT[LC-1]);
			else
			atrib(N[LC][x],N[LC-1][x-1]);
			adun(NT[LC],N[LC][x]);
		}
	}
	adun(sol,NT[L]);
	adun(sol,AT[L]);
	printez(sol);
	LC=L;
	if(mic(AT[L],k)){scad(k,AT[L]);CC=1;}
	for(;;)
	{
		if(!LC)return;
		if(CC==0)
		{
			for(x=a;;x--)
			{
				if(x>LC)continue;
				if(mic(A[LC][x],k))scad(k,A[LC][x]);
				else break;
			}
			LC-=x;CC=1;
			for(;x;x--)printf("0");
		}
		else
		{
			for(x=1;;x++)
			{
				if(mic(N[LC][x],k))scad(k,N[LC][x]);
				else break;
			}
			LC-=x;CC=0;
			for(;x;x--)printf("1");
		}
		if(!LC)break;
	}
}
void init1(int *u)
{
	u[0]=u[1]=1;
}
void atrib(int *u,int *v)
{
	int j,LL=v[0];
	for(j=0;j<=LL;j++)u[j]=v[j];
}
void adun(int *u,int *v)
{
	int j,LL;LL=u[0]>v[0]?u[0]:v[0];
	for(j=1;j<=LL;j++)u[j]+=v[j];
	for(j=1;j<=LL;j++)if(u[j]>9){u[j+1]++;u[j]-=10;}
	if(u[LL+1])LL++;
	u[0]=LL;
}
void printez(int *u)
{
	int j,LL=u[0];
	if(!LL){printf("0\n");return;}
	for(j=LL;j;j--)printf("%d",u[j]);
	printf("\n");
}
int mic(int *u,int *v)
{
	int LL;
	LL=u[0]>v[0]?u[0]:v[0];
	for(;LL;LL--)if(u[LL]-v[LL])return u[LL]<v[LL]?1:0;
	return 0;
}
void scad(int *u,int *v)
{
	int j,LL=u[0];
	for(j=1;j<=LL;j++)u[j]-=v[j];
	for(j=1;j<=LL;j++)if(u[j]<0){u[j]+=10;u[j+1]--;}
	for(j=LL;j>=0;j--)if(u[j])break;
	u[0]=j;
}