配点 : {500} 点
問題文
S_{n,m} 该值应乘以 n 字符
是由 0 和
按字典顺序比较 m 字符
是由 1 组成的长度 n+m 中所有字符串的集合。
s_1, s_2\in S_{n,m} , s_1, s_2 距离 d(s_1, s_2) 彼此相邻 2 转置字符的字符串 定义为“排序 s_1 对 s_2 所需的最少操作数”。 如果
另外, s_1, s_2\in S_{n,m} ,f(s_1,s_2) 定义如下。 您将获得
- d(s_1,t)=d(s_2,t) 的字符串 输出 t\in S_{n,m} 存在,则返回字典顺序最小的此类字符串。如果不存在这样的字符串,则 一组字符串,使得 -1 。
正整数 n,m 和字符串 使用字典比较来比较 T \in S_{n,m} 。 对于 f(s_1,s_2)=T 一组字符串使得 (s_1,s_2)\ (s_1, s_2\in S_{n,m}) ? 到 998244353 求以 的余数。
制約
- 1\leq n,m\leq 30
- n,m 是一个整数
- T\in S_{n,m}
入力
输入是按以下格式从标准输入给出的。
n m T
出力
答案 请打印除以 998244353 取余的结果。 由于是
入力例 1
2 2 0101
出力例 1
4
(s_1,s_2)=( 0011 , 0110 ),(0011 , 1001 ),( 0110 , 0011 ),( 1001 , 0011 ) 满足条件。
例如, (s_1,s_2)=( 0011 , 0110 ) ,
当我输入d(s_1, t)=d(s_2, t) 小于 t\in S_{2,2} 是
您也可以写 0101 和
按字典顺序比较 1001 ,其中按字典顺序最小的是
使用 0101 ,f(s_1, s_2)= 0101 。
入力例 2
4 1 00100
出力例 2
4
(s_1,s_2)=( 00001 , 10000 ),(00010 , 01000 ),( 01000 , 00010 ),( 10000 , 00001 ) 满足条件。
入力例 3
3 3 111000
出力例 3
0
入力例 4
6 4 0001111000
出力例 4
1254