#5376. [2018国家集训队互测]完美的旅行

内存限制:512 MiB 时间限制:80 Sec

题目描述

小A有一张n个点的图,点的标号为0到n-1。点i到点j有Ai,j条有向边。可能有自环。现在小A要在图上进行若干次
旅行。每次旅行都是选任意一个起点,走至少一步,走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号
按位与的值。好奇的小B想要知道:对于所有x∈[1,m]和y∈[0,n),小A进行了若干次旅行,总共走了x步,且所有
旅行的愉悦值的按位与为y的方案数。两种方案不同当且仅当旅行次数不同或某一次旅行不完全相同。为了防止输
出过多,你只需要输出这n×m个数对998244353取模后的结果的按位异或值。为方便起见,保证n是2的幂次。

输入格式

第一行两个数n,m。
后面一个n×n的矩阵,第i行第j列的数表示点i-1到点j-1的有向边的数量。
对于所有数据,2≤n≤64,1≤m≤20000,0≤Ai,j<998244353,保证n是2的幂。

输出格式

输出一个数表示n×m个答案取模后的异或值。

样例

样例输入


			
2 3
1 2
3 4

样例输出


			
1770
样例解释
走 1 步,愉悦值的按位与 =0,1 的方案数分别为 6,4。
走 2 步的方案数分别为 116,38。
走 3 步的方案数分别为 2012,358。
异或值为 1770。

数据范围与提示