矩阵快速幂
设答案为f(i)
举个例子：
当i==2时，包含0的值有：10，20，30，40，50，60，70，80，90，100；0的个数为11，f(2)=11;
i==3时;可以从i==2的情况递推，
第一步：i==2时的数据范围：1-100；在这100个数后面补0；补0后，这些数在1-1000的范围之内，合法，0的个数增加了100个，也就是10^(i-1)；
第二步：把i==2时包含0的有效值拿出来，在这些值后面补0，1，2，3，4，5，6，7，8，9；
比如70；补数之后就成了:700,701,702,703,704,705,706,707,708,709;这样70里面0的个数就被计算了10次。至于700里面由于后面补零增加的一个0，这个可以发现已经在第一步中计算过了。因此加上10*f(i-1);
但要知道100后面补数的话，1001，1003，1003，1004，1005，1006，1007，1008，1009都是不合法的。不合法的情况有9种，每种里面包含0的个数为(i-1)。
因此递推式为f(i)=10*f(i-1)+10^(i-1)-9*(i-1);
接下来就可以愉快的矩阵快速幂了。
#include<bits/stdc++.h>
using namespace std;
int f[];
#define ll long long
ll mod;
ll res[][];
ll ans[];
void Ans()
{
ll tmp[]={};
for(int i=;i<;++i)
{
for(int j=;j<;++j)
{
tmp[i]=(tmp[i]+res[i][j]*ans[j])%mod;;
}
}
for(int i=;i<;++i)ans[i]=tmp[i];
}
void A()
{
ll tmp[][]={};
for(int i=;i<;++i)
{
for(int j=;j<;++j)
{
for(int k=;k<;++k)tmp[i][j]=(tmp[i][j]+res[i][k]*res[k][j])%mod;
}
}
for(int i=;i<;++i)for(int j=;j<;++j)res[i][j]=tmp[i][j];
}
void init(ll n)
{
--n;
res[][]=%mod;res[][]=%mod;res[][]=(-%mod+mod)%mod;
res[][]=%mod;
res[][]=res[][]=;
res[][]=;
for(int i=;i<;++i)ans[i]=;
while(n){
if(n&)Ans();
n>>=;A();
}
cout<<ans[]<<endl;
}
int main()
{
/*
f[1]=1;
for(int i=2;i<=6;++i){
f[i]=10*f[i-1]+pow(10,i-1)-9*(i-1);
cout<<f[i]<<endl;
}
*/
freopen("zeroes.in","r",stdin);
freopen("zeroes.out","w",stdout);
ll k;
cin>>k>>mod;
if(mod==)cout<<<<endl;
else init(k);
}