Puzzle loop

Given a grid with n*m grid points and (n-1)*(m-1) blocks. There may be a number of 0 or 1 in some block, represents the number of lines surround this block is odd or even.(0 for even and 1 for odd) When there is no number, there is no limit to the number of lines surround this block.

You have to draw lines between the grid points to form several cycles (a cycle in the grid is a non-empty trail in which the only repeated grid points are the first and last grid points). Two cycles can share grid points but can not share lines.

Please find the number of different solution modulo 998244353. When a line exists in one solution and does not exist in the other solution, the two solutions are considered different.

The first line contains a single integer t (t<=100) representing the number of test cases in the input. Then t test cases follow.

The first line of each test case contains two integers n and m (2<=n,m<=17) representing the height and width of the grid.

Then n-1 lines followed. The i-th of these lines contains m-1 integers, representing the number in the grid. If there is no number, use '.' instead.

The number of test witch n, m>=10 does not exceed 5.

For each test case, print one integer in one line, which is the answer modulo 998244353.

2
3 3
01
1.
3 4
111
1..

4
4

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）