分数 : $1700$ 分

问题陈述

您有两个字符串 $A = A_1 A_2 ... A_n$ 和 $B = B_1 B_2 ... B_n$，它们的长度相同，均由 $0$ 和 $1$ 组成。$A$ 和 $B$ 中的 $1$ 的数量相等。

您决定使用以下算法变换 $A$：

• 令 $a_1, a_2, ..., a_k$ 为 $A$ 中 $1$ 的索引。
• 令 $b_1, b_2, ..., b_k$ 为 $B$ 中 $1$ 的索引。
• 用随机的排列替换 $a$ 和 $b$，独立且均匀地选择。
• 对于每个 $i$ 从 $1$ 到 $k$，按顺序交换 $A_{a_i}$ 和 $A_{b_i}$。

设 $P$ 为上述过程中字符串 $A$ 和 $B$ 变得相等的概率。

令 $Z = P \times (k!)^2$。显然，$Z$ 是一个整数。

找出 $Z$ 对 $998244353$ 的模。

约束条件

• $1 \leq |A| = |B| \leq 10,000$
• $A$ 和 $B$ 由 $0$ 和 $1$ 组成。
• $A$ 和 $B$ 中的 $1$ 的数量相同。
• $A$ 和 $B$ 至少包含一个 $1$。

部分得分

• 通过满足 $1 \leq |A| = |B| \leq 500$ 的测试集将获得 $1200$ 分。

输入

输入来自标准输入，格式如下：

$A$

$B$

输出

打印 $Z$ 对 $998244353$ 的模的值。

1010
1100

3

在前两步之后，$a = [1, 3]$ 和 $b = [1, 2]$。在打乱 $a$ 和 $b$ 后，有 $4$ 种可能的情况：

• $a = [1, 3]$，$b = [1, 2]$。最初，$A = 1010$。在 swap($A_1$, $A_1$) 之后，$A = 1010$。在 swap($A_3$, $A_2$) 之后，$A = 1100$。
• $a = [1, 3]$，$b = [2, 1]$。最初，$A = 1010$。在 swap($A_1$, $A_2$) 之后，$A = 0110$。在 swap($A_3$, $A_1$) 之后，$A = 1100$。
• $a = [3, 1]$，$b = [1, 2]$。最初，$A = 1010$。在 swap($A_3$, $A_1$) 之后，$A = 1010$。在 swap($A_1$, $A_2$) 之后，$A = 0110$。
• $a = [3, 1]$，$b = [2, 1]$。最初，$A = 1010$。在 swap($A_3$, $A_2$) 之后，$A = 1100$。在 swap($A_1$, $A_1$) 之后，$A = 1100$。

在 $4$ 种情况下，有 $3$ 种结果是 $A = B$。因此，$P = 3 / 4$，$Z = 3$。

01001
01001

4

没有任何交换会改变 $A$，所以我们始终有 $A = B$。

101010
010101

36

每种可能的三次交换序列都将 $A$ 中的 $1$ 放置到正确的位置。

1101011011110
0111101011101

932171449