#include<bits/stdc++.h> #define int long long using namespace std; const int mod=998244353; const int maxn=2e5+7; int n,w; int L; int a[maxn]; inline int qpow(int a,int b){ int ans=1; while(b){ if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } inline int inv(int x){ return qpow(x,mod-2); } vector<int> Lp; void slv25(){ for(int i=1;i<=L;i++){ if(a[i]%w==0)Lp.push_back(i); } int val=0; for(auto x:Lp){ val=(val+qpow(2,x-1))%mod; } int cof=(qpow(2,n*L)-1)*inv(qpow(2,L)-1)%mod; val=val*cof%mod; val=(val+1)%mod; cout<<val<<endl; return; } struct Mat{ int M[3][3]; void clr(){ memset(M,0,sizeof(M)); } void I(){ clr(); for(int i=0;i<3;i++)M[i][i]=1; } }; Mat operator*(const Mat A,const Mat B){ Mat C; C.clr(); for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ for(int k=0;k<3;k++){ C.M[i][j]=(C.M[i][j]+A.M[i][k]*B.M[k][j]%mod)%mod; } } } return C; } Mat Mqp(Mat A,int k){ Mat res;res.I(); while(k){ if(k&1)res=res*A; A=A*A; k>>=1; } return res; } Mat A0,A1,A2; void init(){ A0.clr(),A1.clr(),A2.clr(); A1.M[0][0]=A1.M[0][2]=A1.M[1][1]=A1.M[1][0]=A1.M[2][2]=A1.M[2][1]=1; A2.M[0][0]=A2.M[1][1]=A2.M[2][2]=A2.M[0][1]=A2.M[1][2]=A2.M[2][0]=1; A0.M[0][0]=A0.M[1][1]=A0.M[2][2]=2; } void slv3(){ init(); int C0=0; int C1=0; int C2=0; for(int i=1;i<=L;i++){ C0+=(a[i]%3==0)*n; C1+=(a[i]%3==1)*n; C2+=(a[i]%3==2)*n; } Mat T;T.I(); T=T*Mqp(A0,C0); T=T*Mqp(A1,C1); T=T*Mqp(A2,C2); cout<<T.M[0][0]<<endl; } signed main(){ freopen("string.in","r",stdin); freopen("string.out","w",stdout); cin>>n>>w; string s; cin>>s; L=s.length(); for(int i=1;i<=L;i++)a[i]=s[i-1]-'0'; if(w==2||w==5)slv25(); else slv3(); }