#include<cstdio> #include<vector> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<ctime> #include<cstdlib> using namespace std; int sol,mod,n,i,j,k,nr,fac[100009],inv[100009],ap[13]; char sir[100009]; vector < int > v[12]; vector < int > :: iterator it; int pow(int a,int b) { int i,p=1; for(i=0;(1<<i)<=b;i++) { if(b&(1<<i)) p=(1LL*p*a)%mod; a=(1LL*a*a)%mod; } return p; } int comb(int n,int k) { int p=fac[n]; p=(1LL*p*inv[k])%mod; p=(1LL*p*inv[n-k])%mod; return p; } void add(int &x,int cat) { x+=cat; if(x>=mod) x-=mod; } int main() { freopen("div4.in","r",stdin); freopen("div4.out","w",stdout); gets(sir+1); scanf("%d",&k); mod=1000003; n=strlen(sir+1); if(k==n-1) { sol=0; for(i=1;i<=n;i++) if((sir[k]-48)%4==0) sol++; printf("%d\n",sol); return 0; } fac[0]=inv[0]=1; for(i=1;i<=n;i++) { fac[i]=(1LL*fac[i-1]*i)%mod; inv[i]=pow(fac[i],mod-2); } for(i=1;i<10;i++) for(j=1;j<10;j++) if((j*10+i)%4==0) v[i].push_back(j); for(i=1;i<=n;i++) { if(k-(n-i)>=0&&i-2>=k-(n-i)) { for(it=v[sir[i]-48].begin();it!=v[sir[i]-48].end();it++) add(sol,(1LL*ap[*it]*comb(i-2,k-(n-i)))%mod); } ap[sir[i]-48]++; } printf("%d\n",sol); return 0; }