题目描述

对于一个正整数序列 $a$，定义它的最大权独立集权值为：从 $a$ 中选择若干个互不相邻的数，使所选数字之和最大；这个最大值即为该序列的最大权独立集权值。

如果序列 $a$ 的最大权独立集权值恰好等于 $a$ 中所有数字之和的一半，则称 $a$ 是坏的；否则称 $a$ 是好的。

如果正整数序列 $a$ 的任意连续子区间都是好的，则称 $a$ 是极好的。

给定正整数 $n,m$ 以及 $n$ 个正整数集合

其中 $n$ 表示序列 $a$ 的长度，每个集合中的元素都属于 $[1,m]$。

求满足

的极好序列 $a$ 的数量。

答案对 $998244353$ 取模。

输入格式

第一行包含两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行包含 $m$ 个字符，每个字符均为 0 或 1，字符之间用一个空格隔开。

第 $j$ 个字符为 1，表示 $j\in A_i$；否则表示 $j\notin A_i$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

样例输入

3 3
1 1 1
1 0 1
1 1 0

样例输出

4

数据范围与子任务