← 返回题目列表

AtCoder · utpc2022_n

N. 01 弦乐游戏

中文机器翻译题面 查看原题

配点 : 100 点

問題文

整数 N 和 还给出了0 和 按字典顺序比较 1 组成的长度 N 的字符串 T 。 对于 0 和 按字典顺序比较 1 构成,长度为 2N 的字符串 S = s_1 s_2 \ldots s_{2N} 和 按字典顺序比较 T 用来进行游戏,Alice 和 Bob 玩这个游戏。两人从 Alice 开始,交替进行以下操作,直到所有S 的字符都被标记。选择

  • 1 \le i \le 2N 的整数 选择 i ,并不是表示“等于”的意思s_i 中尚未被标记的一个。然后,如果是
    • Alice 的回合,就在该位数上 o 做标记。如果是
    • Bob 的回合,就在该位数上 x 做标记。如果是

游戏结束时,只从左到右读取标记了o 的位数。N 将文字解释为字符串后,如果在字典顺序上大于或等于 T ,则 Alice 胜利,否则 Bob 胜利。

开始时使用的字符串有 S 的是 2^{2N} 种。在这些中,如果双方都采取对自己获胜最优的策略,Alice 获胜的那部分个数为 998244353 后求余数。

制約

  • N 是一个整数
  • 1 \le N\le 2 \times 10^5
  • T 是 您也可以写 0, 1 组成的长度 N 的字符串

入力

输入是按以下格式从标准输入给出的。

N
T

出力

答案 请打印除以 1 行输出。


入力例 1

1
0

出力例 1

4

0 或 至少 1 组成的长度 要变为 2 的所有字符串均符合。


入力例 2

1
1

出力例 2

3

01, 10, 11 可以得到第 3 个符合条件。


入力例 3

12
011011000111

出力例 3

13225655