#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=999911659;
const int N=510;
int vis[N];
LL inv[10],g[N],f[N][10][N];
inline LL C(LL x,LL y)
{
    LL ans=1;
    for(LL i=x-y+1;i<=x;i++) ans=ans*i%mod;    for(LL i=1;i<=y;i++) ans=ans*inv[i]%mod;
    return ans;
}
int main()
{
    inv[1]=1; for(int i=2;i<=8;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;//计算逆元 
    int p,now=0,pos=0,q1; LL n,ans=0;    scanf("%lld%d",&n,&p);
    memset(vis,-1,sizeof(vis)),vis[0]=0;
    for(int i=1;i<=n;i++)
    {
        now=(now*10+1)%p;
        if(vis[now]==-1) vis[now]=i,g[now]++;
        else{ pos=i; break; }
    }
    if(pos)    {
        int len=pos-vis[now],maxn;
        LL rest=n-(pos-1),cnt;
        cnt=rest/len,maxn=rest%len;
        for(int i=pos;i<=pos+len-1;i++)
        {
            if((i-pos+1)%len==maxn) q1=now;
            (g[now]+=cnt+(i-pos+1<=maxn))%=mod;
            now=(now*10+1)%p;
        }    }
    f[0][0][0]=1;//取第i+1个余数，即i 
    for(int i=0;i<p;i++)
        for(int j=0;j<=8;j++)
            for(int k=0;k<p;k++)
                for(int t=0;t<=8-j;t++)
                    (f[i+1][j+t][(k+(t*i))%p]+=f[i][j][k]*C(g[i]+t-1,t)%mod)%=mod;
    for(int i=0;i<=8;i++)
        ans=(ans+f[p][i][p==1?0:p-q1])%mod;
    printf("%lld\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=999911659;
const int N=510;
int vis[N];
LL inv[10],g[N],f[N][10][N];
inline LL C(LL x,LL y)
{
    LL ans=1;
    for(LL i=x-y+1;i<=x;i++) ans=ans*i%mod;
    for(LL i=1;i<=y;i++) ans=ans*inv[i]%mod;
    return ans;
}
int main()
{
    inv[1]=1; for(int i=2;i<=8;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;//计算逆元 
    int p,now=0,pos=0,q1; LL n,ans=0;
    scanf("%lld%d",&n,&p);
    memset(vis,-1,sizeof(vis)),vis[0]=0;
    for(int i=1;i<=n;i++)
    {
        now=(now*10+1)%p;
        if(vis[now]==-1) vis[now]=i,g[now]++;
        else{ pos=i; break; }
    }
    if(pos)
    {
        int len=pos-vis[now],maxn;
        LL rest=n-(pos-1),cnt;
        cnt=rest/len,maxn=rest%len;
        for(int i=pos;i<=pos+len-1;i++)
        {
            if((i-pos+1)%len==maxn) q1=now;
            (g[now]+=cnt+(i-pos+1<=maxn))%=mod;
            now=(now*10+1)%p;
        }
    }
    f[0][0][0]=1;//取第i+1个余数，即i 
    for(int i=0;i<p;i++)
        for(int j=0;j<=8;j++)
            for(int k=0;k<p;k++)
                for(int t=0;t<=8-j;t++)
                    (f[i+1][j+t][(k+(t*i))%p]+=f[i][j][k]*C(g[i]+t-1,t)%mod)%=mod;
    for(int i=0;i<=8;i++)
        ans=(ans+f[p][i][p==1?0:p-q1])%mod;
    printf("%lld\n",ans);
    return 0;
}