#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int maxn=;

 const long long modn=;

 char ch[maxn];

 int m,n;

 struct mat{

     long long e[][];

     mat(){memset(e,,sizeof(e));}

     void cle(){

         for(int i=;i<=m;i++)e[i][i]=;

     }

 };mat ten[],f[maxn][maxn],g[maxn];

 mat mul(mat x,mat y){

     mat z;

     for(int i=;i<=m;i++){

         for(int j=;j<=m;j++){

             for(int k=;k<=m;k++){

                 z.e[i][j]+=x.e[i][k]*y.e[k][j];

                 z.e[i][j]%=modn;

             }

         }

     }

     return z;

 }

 mat plu(mat x,mat y){

     mat z;

     for(int i=;i<=m;i++){

         for(int j=;j<=m;j++){

             z.e[i][j]=x.e[i][j]+y.e[i][j];

             z.e[i][j]%=modn;

         }

     }

     return z;

 }

 mat pow(mat x,long long k){

     mat z;z.cle();

     while(k){

         if(k&)z=mul(x,z);

         k/=;x=mul(x,x);

     }

     return z;

 }

 int main(){

     scanf("%s%d",&ch,&m);n=strlen(ch);

     ten[].cle();

     for(int i=;i<m;i++)ten[].e[i][i+]=;

     for(int i=;i<=m;i++)ten[].e[m][i]=;

     for(int i=;i<=;i++)ten[i]=pow(ten[],i);

     for(int i=n;i>=;i--){

         f[i][i-].cle();

         for(int j=i;j<=n;j++){

             int z=ch[j-]-'';

             f[i][j]=mul(pow(f[i][j-],),ten[z]);

         }

     }g[n+].cle();

     for(int i=n;i>=;i--){

         for(int j=i;j<=n;j++){

             g[i]=plu(g[i],mul(g[j+],f[i][j]));

         }

     }

     printf("%I64d\n",g[].e[m][m]);

     return ;

 }