AT_tupc2022_o Equidistant Binary String

设 $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)$ 为：把字符串 $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}$ 时，返回这些 $t$ 中字典序最小的那个；如果不存在这样的 $t$，则返回 $-1$。 --- 给定正整数 $n,m$，以及字符串 $T \in S_{n,m}$。试求，有多少对字符串 $(s_1, s_2)\ (s_1, s_2\in S_{n,m})$ 满足 $f(s_1,s_2)=T$。请输出答案对 $998244353$ 取模。

输入为一行，格式如下： > $n\ m\ T$

输出一个整数，表示满足要求的 $(s_1, s_2)$ 对数，对 $998244353$ 取模。

### 样例解释 1 $(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 $(s_1,s_2)=($ `00001` $,$ `10000` $),($ `00010` $,$ `01000` $),($ `01000` $,$ `00010` $),($ `10000` , `00001` $)$ 满足条件。 # 限制 - $1\leq n, m\leq 30$ - $n,m$ 为整数 - $T\in S_{n,m}$ 由 ChatGPT 5 翻译