题目描述

现在给你一个整数$N$和一个二进制数$X$，对$0 \sim X$之间的每个整数$K$在返回到其原始值之前，需要执行多少次下面的操作：

如果$K$是奇数

$K=(K-1) \div 2$

如果$K$是偶数

$K=(K \div 2)+2^{N-1}$

当 $K$ 不可能返回原始值不计入操作次数。

输入格式

第一行输入一个整数$N$，第二行输入一个$N$位的整数$X$。

输出格式

一个整数，表示$0 \sim X$之间的每个整数$K$在返回到其原始值之前，需要执行的操作次数的总和。

由于答案可能过大,请对最终答案$mod \text{ 998244353}$。

样例 1

输入

3
111

输出

40

样例 2

输入

6
110101

输出

616

样例 3

输入

30
001110011011011101010111011100

输出

549320998

说明/提示

• $1 \le N \le 2 \times10^5$
• $0 \le X < 2^N$
• $X$是一个长度为$N$的二进制数($X$的数位不足$N$时用前导$0$补齐)
• 所有数字都是整数

例如,$K = 3$时，操作为：1，0，4，6，7，3，所以$K=3$时答案是$6$。