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.

Input

Input is given from Standard Input in the following format:

A
B

Output

Print the value of Z modulo 998244353.

Examples

Input

1010
1100

Output

3

Input

01001
01001

Output

4

Input

101010
010101

Output

36

Input

1101011011110
0111101011101

Output

932171449

见题面

见题面