#include using namespace std; #include using namespace atcoder; using mint = modint998244353; int main() { int N; string S; cin >> N >> S; mint ans = 0; for (int k = 0; k < N; k++) { /* 愚直 dp[i] := i 文字目まで見たとき、2^k の位がどれも立って**いない**仕切りの入れ方 vector dp(N + 1, 0); dp.at(0) = 1; if (i - k < 0 || S.at(i - k) == '0') { for (ll j = 0; j <= i; j++) dp.at(i + 1) += dp.at(j); } else { for (ll j = i - k + 1; j <= i; j++) dp.at(i + 1) += dp.at(j); } */ vector dp(N + 1, 0); // 上の dp の累積和をとったもの dp.at(0) = 1; for (int i = 0; i < N; i++) { if (i - k < 0 || S.at(i - k) == '0') dp.at(i + 1) = 2 * dp.at(i); else dp.at(i + 1) = 2 * dp.at(i) - dp.at(i - k); } ans += (mint(2).pow(N - 1) - (dp.at(N) - dp.at(N - 1))) * mint(2).pow(k); } cout << ans.val() << endl; }