You and your Pikmin friends have to plant flowers all across the world. For today's mission, you need to plan flowers in a grid with $$$r$$$ rows and $$$c$$$ columns. At each grid location, you can either choose to plant a flower there or not. However, there are $$$k$$$ forbidden patterns that you aren't allowed to make! Each forbidden pattern has $$$r$$$ rows and $$$2$$$ columns. If this pattern exists anywhere in the $$$r \times c$$$ grid, then the entire pattern is invalid. You are curious as to how many different grids you can create that don't violate any pattern. Because this may be large, output the answer mod $$$998244353$$$.
The first line contains three space-separated integers $$$r$$$, $$$c$$$, and $$$k$$$ ($$$1 \leq r \leq 6, 2 \leq c \leq 10^{18}, 0 \leq k \leq 2^{2r}$$$) — the number of rows and columns of the grid, and the number of forbidden patterns, respectively.
Then, $$$k$$$ sets of $$$r$$$ lines follow. In each group of $$$r$$$ lines, the $$$i$$$th line consists of two characters $$$c_{i, 0}$$$ and $$$c_{i, 1}$$$ ($$$c_{i, j} \in \{\texttt{'#'}, \texttt{'.'}\}$$$). Each of these groups of lines represents a forbidden pattern. If $$$c_{i, j} = \texttt{'#'}$$$, then that grid element in the $$$i$$$th row and the $$$j$$$th column is a flower in the forbidden pattern. Otherwise, that grid element is empty.
It is guaranteed that each forbidden grid pattern is unique.
Output the number of possible grids without forbidden patterns, mod $$$998244353$$$.
2 3 1####
57
4 1000000000000000000 2###..#..##..##..
208293190
