#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 505, MAXLOG = 25;
const ll Mod = 999911659;
ll n, p, w = 20, f[MAXLOG][MAXN][2], g[MAXN], inv[MAXN], h[MAXN][MAXLOG][MAXN], Bit[MAXN];

inline ll Quick_Power(ll x, ll p, ll Mod){
	if(!p)	return 1;
	ll tmp = Quick_Power(x, p>>1, Mod);
	if(p&1)	return tmp*tmp%Mod*x%Mod;
	else	return tmp*tmp%Mod;
}

int main(){
	cin>>n>>p;
	ll x = n;
	for(int i = 1; i <= w; i++, x /= 10)	Bit[i] = x%10;
	g[0] = 1;
	for(int i = 1; i <= p; i++)	g[i] = g[i-1]*10%p;
	f[0][1][1] = f[0][1][0] = 1;
	for(int i = 1; i <= w; i++)
		for(int j = 0; j < p; j++){
			int x = 1;
			for(int k = 1; k <= 10; k++)	x = x*j%p;
			for(int k = 0; k < 10; k++){
				if(k < Bit[i])	(f[i][x*g[k]%p][1] += f[i-1][j][0]) %= Mod;
				if(k == Bit[i])	(f[i][x*g[k]%p][1] += f[i-1][j][1]) %= Mod;
				(f[i][x*g[k]%p][0] += f[i-1][j][0]) %= Mod;
			}
		}
//	for(int i = 0; i < p; i++)	cout<<f[w][i][1]<<" "; puts("");
	inv[0] = 1;
	for(int i = 1; i <= 8; i++)	inv[i] = Quick_Power(i, Mod-2, Mod)%Mod;
	h[0][0][0] = 1;
	for(int i = 0; i < p; i++)
		for(int j = 0; j <= 8; j++)
			for(int k = 0; k < p; k++){
				ll ans = 1;
				for(int t = 0; t <= j; t++){
					(h[i+1][j][k] += h[i][j-t][(k-i*t%p+p)%p]*ans) %= Mod;
					ans = ans*(f[w][i][1]+t)%Mod*inv[t+1]%Mod;
				}
			}
//	for(int i = 0; i < p; i++)
//		for(int j = 0; j <= 8; j++)
//			for(int k = 0; k < p; k++)	cout<<i<<" "<<j<<" "<<k<<"  "<<h[i][j][k]<<endl;
	int tmp = (p-Quick_Power(10, n, p)+9)%p;
//	cout<<tmp<<endl;
	cout<<h[p-1][8][tmp];
	
	return 0;
}
/*
我猜还是矩阵乘法（不对，n^3 就已经爆 1e8 了）
f[j][i][k]：数码为 i，第 j 位，模 p 余 k
f[j+1][t][(k+t)%p] += f[j][i][k], t >= i
如果 p <= 10 的话这倒是可以矩阵乘法计算（为了避免爆栈，不要写递归ksm）
而当 p > 10 的话这实际可以线性递推出来，因为每个状态唯一对应一个前驱……
并不正确。因为 k 虽然一样，可能存在多个 i

或许注意力偏了，这本质是一道数论题
111...11 = (10^len-1)/9
经过推导，有：9*10^n - 1 = \sum_{i=1}^8 10^{x_i}, 0 <= x_i <= n 且 x_i 单调递增 
然后可以设法算出 f[x] 表示 10^y mod p = x 的个数
怎么算？其实可以数位 DP
那么如何求出最终的 x_i 可重集？
如果没有 x_i 是集合的限制，其实很简单。 
钦定一个数 v_i 为最小值，然后将它提出来，继续处理剩下的数——但这么做，上界无法保证。
或许可以尝试容斥？不可以。

式子推错了（
\sum_{i=1}^8 10^{x_i} = -10^n+9，0 <= x_i <= n 且 x_i 单调递增

如果没有 x_i 是多重集的限制，其实有一个简单 DP：
h[i][j] 表示前 i 个数码，余数为 j，然后通过枚举这一位填的余数 k 转移
这里有一个奇妙 Trick：如果我们最开始就枚举转移 k，就可以等同于枚举集合（类似多重背包）
但同一 k 的方案之间仍可能存在重复，需要处理如下问题：
现有 a 种物品，你要从中选出 b 个，每种物品数量不限，求方案数
多重集的组合数（无限）
可以等价为 (1+x+x^2+...+x^b)^a[x^b]
其实已经可以用生成函数了，但能不能再简单一点？
 = (1-x)^(-a)[x^b]
再用二项式定理展开：
\sum_{i=0}^inf (-1)^i a^{i上升幂}/i! (-x)^i = \sum_{i=0}^inf a^{i上升幂}/i! x^i
那么答案就是 a^{b 次上升幂}/b!

怎么过不了样例？？？
哦！
如果 9 在模 p 意义下为 0 最开始的结论就不成立
但显然这仅当 p=1/3/9 时有可能
而能被 1/3/9 整除的数有数字和也能被二者整除的特性
有个简单的矩阵快速幂做法：f[i][j][k]：前 j 个数码，数码和模 p 

82749201374821543 5
*/