{"raw_statement":[{"iden":"problem statement","content":"We have a grid $A$ with $N$ rows and $M$ columns. Initially, $0$ is written on every square.  \nLet us perform the following operation.\n\n*   For each integer $i$ such that $1 \\le i \\le N$, in the $i$\\-th row, turn the digits in zero or more leftmost squares into $1$.\n*   For each integer $j$ such that $1 \\le j \\le M$, in the $j$\\-th column, turn the digits in zero or more topmost squares into $1$.\n\nLet $S$ be the set of grids that can be obtained in this way.\nYou are given a grid $X$ with $N$ rows and $M$ columns consisting of `0`, `1`, and `?`.  \nThere are $2^q$ grids that can be obtained by replacing each `?` with `0` or `1`, where $q$ is the number of `?` in $X$. How many of them are in $S$?  \nThis count can be enormous, so find it modulo $998244353$."},{"iden":"constraints","content":"*   $N$ and $M$ are integers.\n*   $1 \\le N,M \\le 18$\n*   $X$ is a grid with $N$ rows and $M$ columns consisting of `0`, `1`, and `?`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$X_{1,1} X_{1,2} \\dots X_{1,M}$\n$X_{2,1} X_{2,2} \\dots X_{2,M}$\n$\\vdots$\n$X_{N,1} X_{N,2} \\dots X_{N,M}$"},{"iden":"sample input 1","content":"2 3\n0?1\n?1?"},{"iden":"sample output 1","content":"6\n\nThe following six grids are in $S$.\n\n011  011  001\n010  011  110\n\n001  011  011\n111  110  111"},{"iden":"sample input 2","content":"5 3\n101\n010\n101\n010\n101"},{"iden":"sample output 2","content":"0\n\n$X$ may have no `?`, and the answer may be $0$."},{"iden":"sample input 3","content":"18 18\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????\n??????????????????"},{"iden":"sample output 3","content":"462237431\n\nBe sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}