Description

一个N*N的上三角矩阵(只有右上一半的值可能不是0)M和另一个整数K。

给M^K的所有元素和及异或和，

在求M^K的过程中的每一步运算要求对998244353取模，

但请注意最后输出的两个数不要求取模

更重要的是：我们保证矩阵对角元素互相不一样且均不为0

Format

Input

第一行两个整数N，K

接下来N行N列整数代表矩阵

1<=N<=500 1<=K<=10^9

Output

一行两个整数，分别代表矩阵元素的和及异或和

Samples

2 1
1 0
0 2

3 3