Description

问题描述：​​

在斯诺克锦标赛中，有一条称为"丁俊晖定律"的规则：

如果一位选手在某一轮击败了丁俊晖，那么该选手在下一轮必定失败（即胜率为 $0\%$）。

从 2024 年球员锦标赛到 2025 年 8 月的上海大师赛，这一定律已经连续 24 站比赛生效。不过，在 2025 年 8 月的武汉公开赛 32 进 16 轮次的比赛中，斯坦・穆迪 5-1 战胜周跃龙，"丁俊晖定律" 被终止。

现在，有 $2^n$ 位选手参加单淘汰赛，选手编号从 $1$ 到 $2^n$（编号从小到大排列）。

小任的编号为 $1$，丁俊晖的编号为 $k$。

​​比赛规则：​​

•每轮比赛前，所有剩余选手按编号从小到大（从左到右）排列。

•然后，将选手分成若干对：第 $1$ 位与第 $2$ 位比赛，第 $3$ 位与第 $4$ 位比赛，以此类推（即每轮中，排序后奇数位置的选手与紧邻其右边的选手比赛）。

•每场比赛淘汰一半选手，直到决出冠军。

•所有选手实力均衡，因此正常情况下，两位选手比赛的胜率各为 $50\%$。

•但是，如果一位选手在上一轮击败了丁俊晖，那么他在本轮比赛的胜率为 $0\%$（即必定失败）。

•注意：丁俊晖本人也可能被淘汰，但定律仅针对击败了丁俊晖的选手（即"弑君者"）在下一轮的表现。

​​问题：​​

给定 $n$ 和 $k$（丁俊晖的编号），求编号为 $1$ 的选手（小任）最终获胜的概率（对 $998244353$ 取模）。

​​补充说明：​​

•锦标赛采用单败淘汰制，共进行 $n$ 轮。

•初始时，所有选手均未击败过丁俊晖。

•只有当一位选手在比赛中击败丁俊晖时，才会成为"弑君者"，并在下一轮拥有 $0\%$ 的胜率（即必定输掉）。

•丁俊晖本人参加比赛时，其胜率规则与其他选手相同。

•我们需要计算小任（编号 $1$）最终获胜的概率，你需要输出对 $998244353$ 取模后的答案，这意味着如果你的答案是 $\frac{a}{b}$（$a$ 和 $b$ 的最大公约数为 $1$），你需要输出 $a \times b^{-1} mod\ 998244353$，其中 $b \times b^{-1} ≡ 1\ (mod\ 998244353)$。

Format

Input

第一行输入一个整数 $n$，表示共有 $2^n$ 个选手，其中 $1\leq n \leq 10^6$。

第二行输入一个长度为 $n+1$ 的二进制字符串，表示 $k$ 的编号(可能包含前导零，保证 $k$ 的大小不超过 $2^n$)。

Output

输出一个整数表示小任获胜概率模 $998244353$ 后的结果。

Samples

1
10

499122177

Limitation

1s, 1024KiB for each test case.