← 返回题目列表

AtCoder · tupc2022_o

O. 等距二进制字符串

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

配点 : {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