{"problem":{"name":"Shuffle and Swap","description":{"content":"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 th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc019_e"},"statements":[{"statement_type":"Markdown","content":"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.\nYou've decided to transform $A$ using the following algorithm:\n\n*   Let $a_1$, $a_2$, ..., $a_k$ be the indices of $1$'s in $A$.\n*   Let $b_1$, $b_2$, ..., $b_k$ be the indices of $1$'s in $B$.\n*   Replace $a$ and $b$ with their random permutations, chosen independently and uniformly.\n*   For each $i$ from $1$ to $k$, in order, swap $A_{a_i}$ and $A_{b_i}$.\n\nLet $P$ be the probability that strings $A$ and $B$ become equal after the procedure above.\nLet $Z = P \\times (k!)^2$. Clearly, $Z$ is an integer.\nFind $Z$ modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq |A| = |B| \\leq 10,000$\n*   $A$ and $B$ consist of $0$ and $1$.\n*   $A$ and $B$ contain the same number of $1$'s.\n*   $A$ and $B$ contain at least one $1$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$A$\n$B$\n\n## Partial Score\n\n*   $1200$ points will be awarded for passing the testset satisfying $1 \\leq |A| = |B| \\leq 500$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc019_e","tags":[],"sample_group":[["1010\n1100","3\n\nAfter the first two steps, $a = [1, 3]$ and $b = [1, 2]$. There are $4$ possible scenarios after shuffling $a$ and $b$:\n\n*   $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$.\n*   $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$.\n*   $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$.\n*   $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$.\n\nOut of $4$ scenarios, $3$ of them result in $A = B$. Therefore, $P = 3$ / $4$, and $Z = 3$."],["01001\n01001","4\n\nNo swap ever changes $A$, so we'll always have $A = B$."],["101010\n010101","36\n\nEvery possible sequence of three swaps puts the $1$'s in $A$ into the right places."],["1101011011110\n0111101011101","932171449"]],"created_at":"2026-03-03 11:01:13"}}