AT_agc019_e.[AGC019E] Shuffle and Swap

有两个长度相同、仅由 $0$ 和 $1$ 组成的字符串 $A = A_1A_2\ldots A_n$ 和 $B = B_1B_2\ldots B_n$。$A$ 和 $B$ 中 $1$ 的个数是相等的。

你决定通过如下的算法改变 $A$：

• 令 $a_1, a_2, \ldots, a_k$ 为 $A$ 中所有 $1$ 出现的位置的下标。
• 令 $b_1, b_2, \ldots, b_k$ 为 $B$ 中所有 $1$ 出现的位置的下标。
• 将 $a$ 和 $b$ 的元素分别独立地均匀随机排列。
• 然后对于每个 $i$（$1 \leq i \leq k$），依次交换 $A_{a_i}$ 和 $A_{b_i}$ 的值。

完成上述步骤后，设 $A$ 和 $B$ 完全相等的概率为 $P$。

进一步定义 $Z = P \times (k!)^2$。显然，$Z$ 是整数。

请输出 $Z$ 对 $998244353$ 取余的结果。

输入为一行，包括两个字符串 $A$ 和 $B$。

输出 $Z$ 对 $998244353$ 取余的结果。

限制

• $1 \leq |A| = |B| \leq 10\,000$
• $A$ 和 $B$ 仅包含 $0$ 和 $1$
• $A$ 和 $B$ 中的 $1$ 的数量相等，且至少有一个 $1$

部分分

• 若能通过 $1 \leq |A| = |B| \leq 500$ 数据集，将获得 $1200$ 分。

样例解释 1

最初的两步后，$a = [1, 3]$，$b = [1, 2]$。将 $a$ 和 $b$ 随机排列后，可能的四种组合如下：

• $a = [1, 3], b = [1, 2]$。初始 $A = 1010$。交换 $A_1$ 和 $A_1$ 后 $A = 1010$。交换 $A_3$ 和 $A_2$ 后 $A = 1100$。
• $a = [1, 3], b = [2, 1]$。初始 $A = 1010$。交换 $A_1$ 和 $A_2$ 后 $A = 0110$。交换 $A_3$ 和 $A_1$ 后 $A = 1100$。
• $a = [3, 1], b = [1, 2]$。初始 $A = 1010$。交换 $A_3$ 和 $A_1$ 后 $A = 1010$。交换 $A_1$ 和 $A_2$ 后 $A = 0110$。
• $a = [3, 1], b = [2, 1]$。初始 $A = 1010$。交换 $A_3$ 和 $A_2$ 后 $A = 1100$。交换 $A_1$ 和 $A_1$ 后 $A = 1100$。

在上述四种结果中，有三种 $A = B$，因此 $P = 3/4$，$Z = 3$。

样例解释 2

通过 $A$ 的元素交换，$A$ 始终不会改变，所以总有 $A = B$。

样例解释 3

无论三次 $A$ 的元素交换如何发生，$A$ 中的 $1$ 总会正确到达目标位置。

由 ChatGPT 5 翻译