设 $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 翻译