题目描述

$0$ と $1$ からなる同じ長さの二つの文字列 $A\ =\ A_1\ A_2\ ...\ A_n$ と $B\ =\ B_1\ B_2\ ...\ B_n$ があります。 $A,\ B$ に含まれる $1$ の個数は等しいです。

あなたは次のアルゴリズムによって $A$ を変化させることにしました。

• $a_1$, $a_2$, ..., $a_k$ を、$A$ で $1$ が出現する位置の添字とする。
• $b_1$, $b_2$, ..., $b_k$ を、$B$ で $1$ が出現する位置の添字とする。
• $a,\ b$ の要素をそれぞれ無作為に並び替える。これらの無作為な並び替えは一様かつ独立である。
• $1$ から $k$ までの各 $i$ に対して、順に $A_{a_i}$ と $A_{b_i}$ の値を入れ替える。

この手順のあと、文字列 $A,\ B$ が一致する確率を $P$ とします。

さらに、$Z\ =\ P\ \times\ (k!)^2$ とします。明らかに、$Z$ は整数です。

$Z$ を $998244353$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$A$ $B$

输出格式

$Z$ を $998244353$ で割った余りを出力せよ。

题目大意

给出两个长度为 $n(n\le 10^4)$ 的 $\texttt{01}$ 串 $A$ 和 $B$。两个串均恰有 $k$ 个 $\texttt{1}$。令 $a_{1, 2, \cdots, k}$ 和 $b_{1, 2, \cdots, k}$ 分别表示 $A$ 和 $B$ 中所有 $\texttt{1}$ 出现的位置。

将 $a$ 和 $b$ 等概率随机排列，按 $i = 1, 2, \cdots, k$ 的顺序交换 $A_{a_i}$ 和 $A_{b_i}$。令 $P$ 表示操作完成后 $A$ 与 $B$ 相等的概率，求 $P\times(k!)^2$ 在模 $998244353$ 意义下的值。

感谢@skylee 提供翻译

1010
1100

3

01001
01001

4

101010
010101

36

1101011011110
0111101011101

932171449

提示

制約

• $1\ \leq\ |A|\ =\ |B|\ \leq\ 10,000$
• $A,\ B$ は $0$ と $1$ からなる。
• $A,\ B$ に含まれる $1$ の個数は等しい。
• $A,\ B$ には $1$ が少なくとも一つ含まれる。

部分点

• $1\ \leq\ |A|\ =\ |B|\ \leq\ 500$ を満たすデータセットに正解すると、$1200$ 点が与えられる。

Sample Explanation 1

最初の二つのステップで、$a\ =\ [1,\ 3]$, $b\ =\ [1,\ 2]$ となります。$a,\ b$ の要素を無作為に並び替えたあとの結果としてありうるものは次の $4$ つです。 - $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$。 この $4$ つの結果のうち、$3$ つで $A\ =\ B$ となっています。よって、$P\ =\ 3$ / $4$ であり、$Z\ =\ 3$ となります。

Sample Explanation 2

$A$ の要素の入れ替えによって $A$ が変化することはなく、したがって必ず $A\ =\ B$ となります。

Sample Explanation 3

三回の $A$ の要素の入れ替えがどのように起こっても、$A$ に含まれる $1$ は適切な位置に移動します。