#include<bits/stdc++.h> #define Rf(i,a,b) for(int i=(a);i<=(b);i++) #define Rb(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; int n,w;string s;int len=0; int mod=998244353; int qp(int a,int b){ int x=1; while(b){ if(b&1) x=1ll*x*a%mod; a=1ll*a*a%mod;b>>=1; }return x; } void slv1(){//w==2,5 int val=0;int tmp=0,p2=1; Rf(i,1,len){ if((s[i]-'0')%w==0){ val=(val+p2)%mod; }tmp++;p2=1ll*p2*2%mod; }int tu=1;Rf(i,1,len) tu=1ll*tu*qp(2,n)%mod; tu=(tu+mod-1)%mod; int td=(qp(2,len)+mod-1)%mod; cout<<((1ll*tu%mod*qp(td,mod-2)%mod*val%mod)+1)%mod; }struct mat{ int H,W;int a[5][5]; mat operator+(const mat &b) const{ mat c;c.H=H,c.W=W; Rf(i,1,H) Rf(j,1,W){ c.a[i][j]=(a[i][j]+b.a[i][j])%mod; }return c; }mat operator*(const mat &b) const{ mat c;c.H=H,c.W=b.W; Rf(i,1,c.H){ Rf(j,1,c.W){ c.a[i][j]=0; Rf(k,1,W){ c.a[i][j]=(c.a[i][j]+(1ll*a[i][k]*b.a[k][j])%mod)%mod; } } }return c; } }; mat qpmt(mat a,int b,mat I){ mat x=I; while(b){ if(b&1) x=x*a; b>>=1;a=a*a; }return x; } void slv2(){ mat f;f.H=1,f.W=3; f.a[1][1]=1,f.a[1][2]=0,f.a[1][3]=0; mat I;I.H=3,I.W=3;Rf(i,1,3)Rf(j,1,3) I.a[i][j]=(i==j); mat tt=I; Rf(i,1,len){ mat tmp=I; int o=(s[i]-'0')%3; Rf(j,1,3){ int ps=j+o; if(ps>3) ps%=3; tmp.a[ps][j]++; }tt=tt*tmp; }f=f*qpmt(tt,n,I); cout<<f.a[1][1]; } int main(){ cin>>n>>w;cin>>s;len=s.length();s=' '+s; if(w==2||w==5) slv1(); else slv2(); return 0; }