#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;
}