{"raw_statement":[{"iden":"problem statement","content":"We have a checkerboard with $H$ rows and $W$ columns, where each square has a `0` or `1` written on it. The current state of checkerboard is represented by $H$ strings $S_1,S_2,\\cdots,S_H$: the $j$\\-th character of $S_i$ represents the digit in the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nSnuke will repeat the following operation.\n\n*   Choose one square uniformly at random. Then, flip the value written in that square. (In other words, change `0` to `1` and vice versa.)\n\nBy the way, he loves an integer sequence $A=(A_1,A_2,\\cdots,A_H)$, so he will terminate the process at the moment when the following condition is satisfied.\n\n*   For every $i$ ($1 \\leq i \\leq H$), the $i$\\-th row from the top contains exactly $A_i$ `1`s.\n\nParticularly, he may do zero operations.\nFind the expected value of the number of operations Snuke does, modulo $998244353$.\nDefinition of the expected value modulo $998244353$It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as an irreducible fraction $\\frac{P}{Q}$, it can also be proved that $Q \\not \\equiv 0 \\pmod{998244353}$. Thus, there uniquely exists an integer $R$ such that $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$. Find this $R$."},{"iden":"constraints","content":"*   $1 \\leq H,W \\leq 50$\n*   $S_i$ is a string of length $W$ consisting of `0`, `1`.\n*   $0 \\leq A_i \\leq W$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$\n$S_1$\n$S_2$\n$\\vdots$\n$S_H$\n$A_1$ $A_2$ $\\cdots$ $A_H$"},{"iden":"sample input 1","content":"1 2\n01\n0"},{"iden":"sample output 1","content":"3\n\nThe process goes as follows.\n\n*   With probability $1/2$, a square with `1` is flipped. The $1$\\-st row now contains zero `1`s, terminating the process.\n*   With probability $1/2$, a square with `0` is flipped. The $1$\\-st row now contains two `1`s, continuing the process.\n    *   One of the squares is flipped. Regardless of which square is flipped, the $1$\\-st row now contains one `1`, continuing the process.\n        *   With probability $1/2$, a square with `1` is flipped. The $1$\\-st row now contains zero `1`s, terminating the process.\n        *   With probability $1/2$, a square with `0` is flipped. The $1$\\-st row now contains two `1`s, continuing the process.\n        *   $\\vdots$\n\nThe expected value of the number of operations is $3$."},{"iden":"sample input 2","content":"3 3\n000\n100\n110\n0 1 2"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"2 2\n00\n01\n1 0"},{"iden":"sample output 3","content":"332748127"},{"iden":"sample input 4","content":"5 4\n1101\n0000\n0010\n0100\n1111\n1 3 3 2 1"},{"iden":"sample output 4","content":"647836743"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}