题解：

一不小心又吊了标算

标算的三进制FWT用的是递归实现，复域用的是$a+b\sqrt 3$而不是$a+b\omega_3$，常数极大，跑了我用时的两倍不止

首先推出数位DP的式子，有点麻烦不想写了。

考虑题目的两个限制。

第一个，集合中的数的出现次数必须是三的倍数，多维三进制循环卷积，好的三进制FWT。

第二份，结果必须是$k$的倍数，$k$进制循环卷积，由于$k$很小，直接暴力做$O(\log n)$次卷积，然后把超过的部分加回去就行了。

于是外层三进制FWT，内层NTT实现$k$进制循环卷积就行了。

注意数位DP里面的转移实际上需要呈上10的若干幂%k。在做循环卷积的时候需要实现出来。

---

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs constusing std::cerr;
using std::cout;cs int mod=998244353;
inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);}
inline int dec(int a,int b){a-=b;return a+(a>>31&mod);}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline int power(int a,int b){int res=1;for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline int power(int a,ll b,int m){int res=1;for(;b;b>>=1,a=a*a%m)(b&1)&&(res=res*a%m);return res;
}
inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;}
inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;}
inline void Mul(int &a,int b){a=mul(a,b);}struct cp{int x,y;cp(){}cp(int _x,int _y=0):x(_x),y(_y){}friend cp operator+(cs cp &a,cs cp &b){return cp(add(a.x,b.x),add(a.y,b.y));}friend cp operator-(cs cp &a,cs cp &b){return cp(dec(a.x,b.x),dec(a.y,b.y));}friend cp operator*(cs cp &a,cs cp &b){int t=mul(a.y,b.y);return cp(dec(mul(a.x,b.x),t),dec(add(mul(a.x,b.y),mul(b.x,a.y)),t));}friend cp operator*(cs cp &a,int b){return cp(mul(a.x,b),mul(a.y,b));}void operator+=(cs cp &b){*this=*this+b;}void operator-=(cs cp &b){*this=*this-b;}void operator*=(cs cp &b){*this=*this*b;}void operator*=(int b){Mul(x,b),Mul(y,b);}
};inline cp w1(cs cp &a){return cp(dec(0,a.y),dec(a.x,a.y));}
inline cp w2(cs cp &a){return cp(dec(a.y,a.x),dec(0,a.x));}int S,invS;
inline void FWT(cp *A){cp x,y,z;for(int re i=1;i<S;i*=3)for(int re j=0;j<S;j+=i*3)for(int re k=0;k<i;++k){x=A[j+k],y=A[j+k+i],z=A[j+k+i*2];A[j+k]=x+y+z;A[j+k+i]=x+w1(y)+w2(z);A[j+k+i*2]=x+w2(y)+w1(z);}
}
inline void IFWT(cp *A){cp x,y,z;for(int re i=1;i<S;i*=3)for(int re j=0;j<S;j+=i*3)for(int re k=0;k<i;++k){x=A[j+k],y=A[j+k+i],z=A[j+k+i*2];A[j+k]=x+y+z;A[j+k+i]=x+w2(y)+w1(z);A[j+k+i*2]=x+w1(y)+w2(z);}for(int re i=0;i<S;++i)A[i]*=invS;
}cs int bit=12,SIZE=1<<bit|1;int r[SIZE],*w[bit+1];
inline void init_NTT(){for(int re i=1;i<=bit;++i)w[i]=new int[1<<i-1];int wn=power(3,mod-1>>bit);w[bit][0]=1;for(int re i=1;i<(1<<bit-1);++i)w[bit][i]=mul(w[bit][i-1],wn);for(int re i=bit-1;i;--i)for(int re j=0;j<(1<<i-1);++j)w[i][j]=w[i+1][j<<1];
}
inline void NTT(cp *A,int len,int typ){for(int re i=0;i<len;++i)if(i<r[i])std::swap(A[i],A[r[i]]);for(int re i=1,d=1;i<len;i<<=1,++d)for(int re j=0;j<len;j+=i<<1)for(int re k=0;k<i;++k){cp &t1=A[j+k],&t2=A[j+k+i],t=t2*w[d][k];t2=t1-t,t1+=t;}if(typ==-1){std::reverse(A+1,A+len);for(int re i=0,inv=power(len,mod-2);i<len;++i)A[i]*=inv;}
}
inline void init_rev(int l){for(int re i=1;i<l;++i)r[i]=r[i>>1]>>1|((i&1)?l>>1:0);
}cs int K=255;ll n;int k,L;
char s[20];int sl;
int pw[20];cp F[K][729],G[729];cp q[SIZE],a[SIZE];inline void mul(cp *a,cp *b,cp *c,ll len){int st=power(10,len,k);//cerr<<"st : "<<st<<"\n";static cp A[SIZE],B[SIZE];memset(A,0,sizeof(cp)*L);memset(B,0,sizeof(cp)*L);for(int re i=0;i<k;++i)B[i]=b[i];for(int re i=0;i<k;++i)A[i*st%k]+=a[i];NTT(A,L,1),NTT(B,L,1);for(int re i=0;i<L;++i)A[i]*=B[i];NTT(A,L,-1);for(int re i=k;i<L;++i)A[i%k]+=A[i];memcpy(c,A,sizeof(cp)*k);
}inline cp calc(){memset(a,0,sizeof(cp)*L);a[0].x=1;ll len=1;for(ll b=n;b;(b>>=1)&&(mul(q,q,q,len),len<<=1))if(b&1)mul(a,q,a,len);return a[0];
}signed main(){
#ifdef zxyoifreopen("glamour.in","r",stdin);
#else
#ifndef ONLINE_JUDGEfreopen("glamour.in","r",stdin);freopem("glamour.out","w",stdout);
#endif
#endifinit_NTT();scanf("%lld%d",&n,&k);scanf("%s",s);sl=strlen(s);pw[0]=1;for(int re i=1;i<=10;++i)pw[i]=pw[i-1]*3;S=pw[sl];invS=power(S,mod-2);for(L=1;L<=((k-1)<<1);L<<=1);init_rev(L);for(int re d=0;d<10;++d){int p=0;for(int re j=0;j<sl;++j)if(s[j]-'0'==d){p+=pw[j];break;}F[d%k][p].x++;}for(int re i=0;i<std::min(k,10);++i)FWT(F[i]);for(int re i=0;i<S;++i){for(int re j=0;j<k;++j)q[j]=F[j][i];G[i]=calc();}IFWT(G);cout<<G[0].x<<"\n";return 0;
}