E - Shuffle and Swap

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : 1700

問題文

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

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

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

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

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

Z998244353 で割った余りを求めてください。

制約

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

部分点

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

入力

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

A
B

出力

Z998244353 で割った余りを出力せよ。


入力例 1

1010
1100

出力例 1

3

最初の二つのステップで、a = [1, 3], b = [1, 2] となります。a, b の要素を無作為に並び替えたあとの結果としてありうるものは次の 4 つです。

  • a = [1, 3], b = [1, 2]。はじめ A = 1010A_1A_1 の入れ替え後 A = 1010A_3A_2 の入れ替え後 A = 1100
  • a = [1, 3], b = [2, 1]。はじめ A = 1010A_1A_2 の入れ替え後 A = 0110A_3A_1 の入れ替え後 A = 1100
  • a = [3, 1], b = [1, 2]。はじめ A = 1010A_3A_1 の入れ替え後 A = 1010A_1A_2 の入れ替え後 A = 0110
  • a = [3, 1], b = [2, 1]。はじめ A = 1010A_3A_2 の入れ替え後 A = 1100A_1A_1 の入れ替え後 A = 1100

この 4 つの結果のうち、3 つで A = B となっています。よって、P = 3 / 4 であり、Z = 3 となります。


入力例 2

01001
01001

出力例 2

4

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


入力例 3

101010
010101

出力例 3

36

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


入力例 4

1101011011110
0111101011101

出力例 4

932171449

Score : 1700 points

Problem Statement

You have two strings A = A_1 A_2 ... A_n and B = B_1 B_2 ... B_n of the same length consisting of 0 and 1. The number of 1's in A and B is equal.

You've decided to transform A using the following algorithm:

  • Let a_1, a_2, ..., a_k be the indices of 1's in A.
  • Let b_1, b_2, ..., b_k be the indices of 1's in B.
  • Replace a and b with their random permutations, chosen independently and uniformly.
  • For each i from 1 to k, in order, swap A_{a_i} and A_{b_i}.

Let P be the probability that strings A and B become equal after the procedure above.

Let Z = P \times (k!)^2. Clearly, Z is an integer.

Find Z modulo 998244353.

Constraints

  • 1 \leq |A| = |B| \leq 10,000
  • A and B consist of 0 and 1.
  • A and B contain the same number of 1's.
  • A and B contain at least one 1.

Partial Score

  • 1200 points will be awarded for passing the testset satisfying 1 \leq |A| = |B| \leq 500.

Input

Input is given from Standard Input in the following format:

A
B

Output

Print the value of Z modulo 998244353.


Sample Input 1

1010
1100

Sample Output 1

3

After the first two steps, a = [1, 3] and b = [1, 2]. There are 4 possible scenarios after shuffling a and b:

  • a = [1, 3], b = [1, 2]. Initially, A = 1010. After swap(A_1, A_1), A = 1010. After swap(A_3, A_2), A = 1100.
  • a = [1, 3], b = [2, 1]. Initially, A = 1010. After swap(A_1, A_2), A = 0110. After swap(A_3, A_1), A = 1100.
  • a = [3, 1], b = [1, 2]. Initially, A = 1010. After swap(A_3, A_1), A = 1010. After swap(A_1, A_2), A = 0110.
  • a = [3, 1], b = [2, 1]. Initially, A = 1010. After swap(A_3, A_2), A = 1100. After swap(A_1, A_1), A = 1100.

Out of 4 scenarios, 3 of them result in A = B. Therefore, P = 3 / 4, and Z = 3.


Sample Input 2

01001
01001

Sample Output 2

4

No swap ever changes A, so we'll always have A = B.


Sample Input 3

101010
010101

Sample Output 3

36

Every possible sequence of three swaps puts the 1's in A into the right places.


Sample Input 4

1101011011110
0111101011101

Sample Output 4

932171449