配点 : 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做标记。如果是
- Alice 的回合,就在该位数上
游戏结束时,只从左到右读取标记了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