20
题目描述
对于每一个 $0\le i,j<4$，给定 $x(i,j)$ 使得：
1. 交换律：$x(i,j)=x(j,i)$
2. 结合律：$x(x(i,j),k)=x(i,x(j,k))$。
3. 单元：$x(0,i)=i$。
定义函数 $f(n)$，使得：
1. $f(p^k)=pk\bmod 4$
2. 当 $\gcd(a,b)=1$，$f(ab)=x(f(a),f(b))$。
特别，$f(1)=0$。
定义函数 $g$ 为：
$$g(n,k,r)=\sum_{i=1}^ni^k[f(i)=r]$$
给定 $m$ 和 $k$，请对所有 $1\le i\le\lfloor\sqrt m\rfloor$，计算所有 $0\le r<4$ 的 $g(\lfloor\frac mi\rfloor,k,r)$ 值。答案对 $998244353$ 取模。
输入输出格式
输入格式
第一行两个整数 $n$，$k$。
接下来 $4$ 行每行 $4$ 个整数，第 $i$ 行第 $j$ 整数为 $x(i-1,j-1)$。
输出格式
输出 $\lfloor\sqrt m\rfloor$ 行。
第 $i$ 行包含四个非负整数，第 $r$ 非负整数为 $g(\lfloor\frac mi\rfloor,k,r)$。
输入输出样例
输入样例 #1
10 0
0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2输出样例 #1
2 2 3 3
2 1 1 1
1 0 1 1输入样例 #2
100 100
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0输出样例 #2
457599333 476580683 403589597 762762658
361221912 612412943 661908092 483645330
242804711 682542199 535167020 465246643
913280460 516845083 917292729 390364642
39265044 919790719 181416471 421087779
530140662 31014314 181416471 226287885
982924733 31014314 851084249 226287885
982924733 938693280 851084249 226287885
982924733 938693280 851084249 435036575
982924733 938693280 851084249 138976409说明
本题不采用捆绑测试，数据略微有梯度。
对于 $16\%$ 的数据，$n\le10^6$。
对于 $100\%$ 的数据，$1\le n\le 10^{10}$，$0\le k\le 1000$。