← 返回题目列表

AtCoder · kupc2019_d

D. 最大最小游戏

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

配点 : 200 点

問題文

2N 有牌。 i~(1 \leq i \leq 2N) 卡包含一个整数 写入 i 。

Chisaki 和 Tsukinose 决定使用这些卡牌玩以下游戏。

  1. 仔细洗牌,N 一次拿一张牌,并组成每位玩家的起始手牌。
  2. 游戏是 N 由回合组成。在每一轮中,2 每位玩家从自己的手牌中选择上面写有最小数字的牌并将其展示给对方。所显示的卡片上写有较高数字的玩家赢得该轮。亮出的牌将从每位玩家的手上移除,并且不会在后续回合中被考虑。

Chisaki-san 和 Tsukinose-san 正在玩这个游戏。 玩了 1 次。

比赛结果是 长度仅由 0 和 按字典顺序比较 1 组成的长度 N 的字符串 S 。 任意整数 当 i\ (1 \leq i \leq N) , 当我输入S_i 是 在 1 时, 千咲正在玩游戏 i 恭喜您成为第二轮的获胜者。S_i 是 在 0 表示其他情况。

Chisaki先生的起手牌有多少种可能会给出这样的游戏结果? 因为答案可能很大,998244353 后的余数。

制約

  • 1 \leq N \leq 10^5
  • S 是 您也可以写 0 和 按字典顺序比较 1 组成的长度 N 字符串。 字符

入力

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

N
S

出力

作为Chisaki的第一手牌,计算可能的牌类型数量。 打印除以 998244353 除以后的余数输出。


入力例 1

2
01

出力例 1

1

千咲第一手牌 1 和 按字典顺序比较 4 是月之濑先生的第一手资料。 考虑这样的情况:有一张卡片上写着 2 和 按字典顺序比较 3 。这时,

  • 1 第二轮,Chisaki-san 月之濑先生收到了一张写有 1 的卡片。 向对方展示写有 2 的卡片,月之濑成为该轮的获胜者。 向对方展示写有
  • 2 第二轮,Chisaki-san 月之濑先生收到了一张写有 4 的卡片。 向对方展示写有 3 的卡片,千咲成为该轮的获胜者。

因此,Chisaki的第一手牌满足给定的游戏结果。


入力例 2

15
111110001011100

出力例 2

2100