题目描述

一张有向无环图被分成了$m$层，第一层只有一个源点，最后一层只有一个汇点，剩下的每一层都有$k$个节点。 我们将第$i$层的第$k$个结点称作$(i,k)$。 现在你可以取反第i(1<i<m-1)层和第$i+1$层之间的所有连边。 也就是把原本从$(i,k_1)$连到$(i+1,k_2)$的边，全部变成从$(i,k_2)$连到$(i+1,k_1)$。 你可以任意选择一些相邻层之间的边取反，也可以都不取反。 请问他有多少种取反的方案，把从源点到汇点的路径数变成偶数条？ 答案对$998244353$取模。

输入

第一行两个整数$m,k$。 接下来$m-1$行, 第一行和最后一行有$k$个整数$0$或$1$，剩下每行有$k^2$个整数$0$或$1$，第 (j-1)×k+t个整数表示($i,j$)到($i+1,t$)有没有边。

输出

一行一个整数表示答案。

输入样例

5 3 
1 0 1 
0 1 0 1 1 0 0 0 1 
0 1 1 1 0 0 0 1 1 
0 1 1

输出样例

4

提示

【数据规模及约定】 对于20%的数据，$m≤10，k≤2$。 对于40%的数据，$m≤10^3，k≤2$。 对于60%的数据，$m≤10^3，k≤5$。 对于100%的数据，$4≤m≤10^4，k≤10$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。