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);
}
