Background

Little F likes to eat Braised Chicken Rice. However, one day he discovers that a mysterious person has placed impassable obstacles on his way to the cafeteria; the obstacles will only disappear if he solves the following problem.

Description

For a sequence of positive integers $a$, the weight of the maximum weight independent set of $a$ is defined as the maximum sum of a subset of $a$ such that no two chosen elements are adjacent. (Definition of adjacency: Let $n$ be the length of $a$. For $1\le i < n$, position $i$ and position $i+1$ are adjacent; no other pairs are adjacent.)

A sequence $a$ is called "bad" if twice the weight of its maximum weight independent set is exactly equal to the sum of all elements in $a$; otherwise, $a$ is called "good".

A sequence $a$ is called "excellent" if every subsegment of $a$ is good. (Definition of subsegment: Let the length of $a$ be $n$. For any $1\le l\le r\le n$, $[a_l, a_{l+1}, \dots, a_r]$ is called a subsegment of $a$.)

Given $n, m$ and $n$ sets of positive integers $A_1 \sim A_n$, where $n$ is the length of $a$ and all numbers in the sets belong to $[1, m]$. How many ways are there to choose $a_i \in A_i$ for each $i$ such that $a$ is excellent? The answer should be modulo $998244353$.

Input

Read data from standard input.

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

The next $n$ lines each contain $m$ characters, where each character is either 0 or 1. If the $j$-th character ($1\le j\le m$) is 1, it means $j\in A_i$; otherwise, $j\notin A_i$. The characters are separated by spaces.

Output

Output to standard output.

Output the answer modulo $998244353$.

Examples

Examples 1 Input

3 3
1 1 1
1 0 1
1 1 0

Examples 1 Output

4

Examples 1 Note

In this example, $A_1=\{1,2,3\}, A_2=\{1,3\}, A_3=\{1,2\}$. The excellent sequences are:

• $[1,3,1]$
• $[2,1,2]$
• $[2,3,2]$
• $[3,1,2]$

Subtasks

All data satisfy: $1\le n\le 200, 1\le m\le 19$.