F. 异或王国

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

知周所众，ICPC2025上海站是名副其实的♛异或王国♛，两个一轮打了都会变成一个零轮。这场比赛有高达 $4$ 题出现了XOR。因此在上个星期，学长在经历 $5$ 个小时的折磨后，"高高兴兴"的拿了铁牌。为了报答清华出的好题，学长决定放个XOR给你们尝尝咸淡。

我们已知异或运算的基本规则是：当两个输入值不同时，输出为 $1$ ；当两个输入值相同时，输出为 $0$ 。对于只能取值为 $0$ 或 $1$ 的 $a$ 和 $b$ ，它们的异或运算公式如下：

$$a\oplus b=\left\{\begin{matrix}0&[a=b]\\1&[a\ne b]\end{matrix}\right.$$

在一些特殊情况下， $a\oplus b$ 的值可以类似于 $a+b$ （比如： $1\oplus 0=1+0$ ），我们叫它 0.o¿状态。

现在我们希望在给定 $a$ 的二进制后，有多少个二进制长度为 $n$ 的 $b$ 与 $a$ 异或会出现 0.o¿状态。

（答案过大，请对 $998244353$ 取模）

每个测试文件仅有一组测试数据。

第一行输入一个正整数 $n$ $(1\le n\le10^5)$ ，表示 $b$ 的二进制长度。

第二行输入一个长度为 $n$ 只包含 $0$ 和 $1$ 的字符串 $s$ ，表示 $a$ 的二进制。

输出一行一个整数，表示会出现 0.o¿状态的 $b$ 的数量对 $998244353$ 取模的结果。

5
10101