Person in Charge

Problem Description

Emiya is a high school student who is good at cooking. He has mastered $n$ kinds of cooking methods and can cook using $m$ kinds of main ingredients. For the sake of convenience, we number the cooking methods from $1$ to $n$ and the main ingredients from $1$ to $m$.

Each dish Emiya makes uses exactly one cooking method and exactly one main ingredient. More specifically, Emiya can make $a_{i,j}$ different dishes that use cooking method $i$ and main ingredient $j$ ($1 \le i \le n$, $1 \le j \le m$), which means Emiya can make a total of $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} a_{i,j}$ different dishes.

Today, Emiya is going to prepare a meal to entertain his good friends Yazid and Rin. However, the three of them have different requirements for the combination of dishes. More specifically, for a combination plan containing $k$ dishes:

• Emiya will not let everyone go hungry, so he will make at least one dish, i.e., $k \ge 1$.
• Rin wants to taste dishes made with different cooking methods, so she requires that each dish uses a distinct cooking method.
• Yazid does not want to taste too many dishes made with the same ingredient, so he requires that each main ingredient is used in at most half of the dishes (i.e., $\lfloor \frac{k}{2} \rfloor$ dishes).

Here, $\lfloor x \rfloor$ is the floor function, representing the largest integer not exceeding $x$.

These requirements do not trouble Emiya, but he wants to know how many different combination plans meet all the requirements. Two plans are different if and only if there is at least one dish that appears in one plan but not in the other.

Emiya has come to you for help. Please calculate the number of valid combination plans modulo the prime number $998,244,353$ and tell him the result.

Input Format

The first line contains two integers $n$ and $m$ separated by a single space.

Lines 2 to $n + 1$ each contain $m$ integers separated by a single space, where the $m$ numbers in line $i + 1$ are $a_{i,1}, a_{i,2}, \cdots, a_{i,m}$ in sequence.

Output Format

Output a single integer on one line, representing the number of valid plans modulo $998,244,353$.

Samples

2 3 
1 0 1
0 1 1

3

3 3
1 2 3
4 5 0
6 0 0

190

Sample 1 Explanation

In this sample, for each pair $(i, j)$, Emiya can make at most one dish, so we directly describe a dish by giving the numbers of the cooking method and main ingredient.

The valid plans include:

• Making one dish with cooking method $1$ and main ingredient $1$, and one dish with cooking method $2$ and main ingredient $2$.
• Making one dish with cooking method $1$ and main ingredient $1$, and one dish with cooking method $2$ and main ingredient $3$.
• Making one dish with cooking method $1$ and main ingredient $3$, and one dish with cooking method $2$ and main ingredient $2$.

Thus, the output result is $3 \bmod 998,244,353 = 3$. Note that all plans containing only one dish are invalid, because the only main ingredient is used in more than half of the dishes, which does not meet Yazid's requirement.

Sample 2 Explanation

Emiya must make at least $2$ dishes.

The number of valid plans with $2$ dishes is $100$.

The number of valid plans with $3$ dishes is $90$.

Therefore, the total number of valid plans is $100 + 90 = 190$.

Sample 3

See meal/meal3.in and meal/meal3.ans in the contestant's directory.

Data Range

For $100\%$ of the data: $1 \le n \le 100$, $1 \le m \le 2000$, $0 \le a_{i,j} \lt 998,244,353$.