#P2502. 规整

规整

题目描述

形式化题面

意识流题面与形式化题面无关,有空的话可以去鉴赏。

给定一个长度为 nn 的 01 串 bb,若存在一个 nn 的排列 aa,满足:对于 ai(2in)a_i(2\le i\le n),记 m=maxj=1i1{aj}m=\max_{j=1}^{i-1}\{a_j\}

  • bi=1b_i=1,则 ai>ma_i>m
  • 否则 ai<ma_i<m

则称 aabb 的一个「PBS (Permutation and Binary String) 排列」,注意到 b1{b_1} 的取值是任意的,对 a{a} 没有影响

现在,小 B 想知道,对于给定的 bb,存在多少个它的「PBS 排列」。

由于结果可能很大,所以你只需要输出结果对 998244353998244353 取模的值。

意识流题面

11 开始,足迹遍及整个长度为 nn01 序列 bb,心也随之逐渐踏过长度也为 nn排列 aa

记当前经过位置的下标为 ii

你初始有一值 m=m0=NaNm=m_0=\text{NaN},你可以认为 xR\forall x\in\textbf Rx>m0,x<m0x>m_0,x<m_0 均成立。

进行一个最大值的比较。心的每次跃进,即 ii+1i\gets i+1,都会自动进行 mmax(m,ai1)m\gets \max(m,a_{i-1})。但如果 i=2i=2,直接进行 mai1m\gets a_{i-1}

自然地引出下面的法则:

bi=1b_i=1,则 ai>ma_i>m;否则 ai<ma_i<m

如果不符合这样的法则,那么视作心已然不合乎你的足迹,将会坠落。

你自然期待千年后依旧璀璨,永不坠落,请回答:

记「不会让你坠落的排列 aa」为一个「PBS 排列」。你想知道对于 bb,存在多少个「PBS 排列」。注意到 b1{b_1} 的取值是任意的,对 a{a} 没有影响

由于结果可能很大,所以你只需要输出结果对 998244353998244353 取模的值。

样例

3
3
111
3
101
4
0101
1
1
2

样例说明

  • 对于数据 11,唯一的 a={1,2,3}a=\{1,2,3\}
  • 对于数据 22,唯一的 a={2,1,3}a=\{2,1,3\}
  • 对于数据 33,存在两个不同的 aaa={1,3,2,4}a=\{1,3,2,4\}a={2,3,1,4}a=\{2,3,1,4\}

提示

对于 100%100\% 的数据,有 1T1041\le T\le 10^42n1062\le n\le 10^6i[1,n],bi{0,1}\forall i\in[1,n],b_i\in\{0,1\}

保证单个测试点内 n2×106\sum n\le 2\times10^6