import std.stdio,std.conv,std.algorithm,std.string;alias L=long;L M=998244353;L[]X;L[L]C;L h(L m,L[]U){L f;foreach(u;U[0..m])f=f*2%M+u;foreach(i,u;U)if(i/m&1^U[i%m]^u)return f+u;return f+1;}void main(){L n=readln.chomp.to!L,b=n*2;foreach(c;readln.chomp)X~=c-'0';for(L d=n|1;d>2;d-=2)if(n%d<1){L c=h(n/d,X);foreach(e,q;C)e%d||(c+=M-q);C[d]=c%M;}n=h(n,X)*b;foreach(d,c;C)n+=M-c*(b-b/d)%M;writeln(n%M);}
