#include<bits/stdc++.h>

#define maxn 200005
#define INF 1e18
#define pii pair<int,int>
#define int long long
#define mod 999911659

using namespace std;

inline int read(){
	int lre=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(isdigit(c)){
		lre=(lre<<3)+(lre<<1)+(c-'0');
		c=getchar();
	}
	return lre*f;
}

inline int quickpow(int a,int b,int p){
	int lre=1;
	while(b){
		if(b&1)lre=(lre*a)%p;
		b>>=1;
		a=(a*a)%p; 
	}
	return lre;
}

int gcd(int a,int b){
	return (b==0)?a:gcd(b,a%b);
}

int n,p;
int inv[20];
int f[550];
int dp[4][15][550];//dp[用了几个][模p余数]

vector<int> v;
int cnt[550];
int visited[550];

int C(int a,int b){
	if(b==0)return 1;
	int lre=1;
	for(int i=1;i<=b;i++){
	//	cout<<"up for "<<a-i+1<<" down for "<<i<<endl;
		lre=(lre*inv[i])%mod;
		lre=(lre*(a-i+1))%mod;
	}
	return lre;
}

inline void add(int &x,int y){
	x=(x+y)%mod;
}

signed main(){
//	cout<<C(2,2)<<endl;
	n=read();p=read();
	//f[i]=i个1在一起
	for(int i=1;i<=10;i++){
		inv[i]=quickpow(i,mod-2,mod);
	}
	v.push_back(1%p);f[1%p]=1;visited[1%p]=true;
	memset(visited,0,sizeof(visited));
	int nxt,beg=-1;
	while(v.size()<=n-1){
		nxt=(v.back()*10+1)%p;
		if(visited[nxt]){
			beg=visited[nxt]-1;
			break;
		}
		visited[nxt]=v.size()+1;
		v.push_back(nxt);
		f[nxt]++;
	}
//	cout<<"beg="<<beg<<endl;
//	cout<<"v:";for(int x:v)cout<<x<<" ";cout<<endl;
	//[beg,v.size()-1]是循环节 
	
	if(beg!=-1){
		memset(cnt,0,sizeof(cnt));
		int len=v.size()-1-beg+1;
		for(int i=beg;i<v.size();i++){
			cnt[v[i]]++;
		}
		for(int k=0;k<p;k++)f[k]+=((n-v.size())/len)*cnt[k];
		int re=(n-v.size())%len;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=re;i++){
			cnt[v[beg+i-1]]++;
		}
		for(int k=0;k<p;k++)f[k]+=cnt[k];
	}
//	cout<<"*"<<endl; 
	
	for(int i=0;i<p;i++){
	//	cout<<"f["<<i<<"]="<<f[i]<<endl;
		f[i]%=mod;
	} 
	
//	exit(0);
	int tmp=0,pre=1;
	dp[pre][0][0]=1;
	for(int x=0;x<=p-1;x++){
	//	memset(dp[tmp],0,sizeof(dp[tmp]));
	//	cout<<"x="<<x<<endl;
		for(int i=0;i<=8;i++){
			for(int j=0;j<=p-1;j++){
				//dp[tmp][i][j]
				//dp[tmp][i][j]=dp[pre][i-k][(i-k*x)%p]*C(f[x],k)
				//k很小，暴力计算 
			//	printf("dp[%lld][%lld][%lld]!\n",x,i,j);
				dp[tmp][i][j]=0;
				for(int k=0;k<=i;k++){
				//	cout<<"k="<<k<<" C(f[x]+k-1,k)=C("<<f[x]+k-1<<","<<k<<")="<<C(f[x]+k-1,k);
				//	cout<<" pre=dp["<<x-1<<"]["<<i-k<<"]["<<(j-(k*x%p)+p)%p<<"]"<<endl;
					add(dp[tmp][i][j],dp[pre][i-k][(j-(k*x%p)+p)%p]*C(f[x]+k-1,k)%mod);
				}
			//	printf("dp[%lld][%lld][%lld]=%lld\n",x,i,j,dp[tmp][i][j]);
			}
		}
		swap(tmp,pre);
	}//81*p^2
	
	int S=(quickpow(10,n,p)-1+p)%p;
	for(int i=0;i<p;i++){
		if((9*i)%p==S){
			S=i;break;
		}
	}
	//此时S是最长后缀的和
	int ans=0;
	for(int i=0;i<=8;i++){
		add(ans,dp[pre][i][(p-S)%p]);
	} 
	printf("%lld\n",ans);
	
	return 0;
}