当前没有测试数据。

5.图的计数

题目描述

一个$DAG$，这个$DAG$有$m$层，第一层只有一个源点，最后一层只有一个汇点，剩下的每一层都有$k$个节点。每次可以取反第$i$层和第$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)\times k+t$个整数表示$(i,j)$到$(i+1,t)$有没有边。

输出格式

一行一个整数表示答案。

数据范围与提示

对于$100\%$的数据，满足$1 < m < 10000$，$1 \leq k \leq 10$。

样例

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