P7572 20

For every $0 \le i, j < 4$, you are given $x(i, j)$ such that: 1. Commutativity: $x(i,j)=x(j,i)$. 2. Associativity: $x(x(i,j),k)=x(i,x(j,k))$. 3. Identity element: $x(0,i)=i$. Define a function $f(n)$ such that: 1. $f(p^k)=pk\bmod 4$. 2. When $\gcd(a,b)=1$, $f(ab)=x(f(a),f(b))$. In particular, $f(1)=0$. Define the function $g$ as: $$g(n,k,r)=\sum_{i=1}^n i^k [f(i)=r]$$ Given $m$ and $k$, for all $1 \le i \le \lfloor \sqrt m \rfloor$, compute the values of $g\left(\left\lfloor \frac{m}{i} \right\rfloor, k, r\right)$ for all $0 \le r < 4$. Take all answers modulo $998244353$.

The first line contains two integers $m$ and $k$. Then follow $4$ lines, each with $4$ integers. The $j$-th integer on the $i$-th line is $x(i-1,j-1)$.

Output $\lfloor \sqrt m \rfloor$ lines. The $i$-th line contains four non-negative integers. The $r$-th integer is $g\left(\left\lfloor \frac{m}{i} \right\rfloor, k, r\right)$.

This problem does not use bundled tests, and the testdata has a slight difficulty gradient. For $16\%$ of the testdata, $m \le 10^6$. For $100\%$ of the testdata, $1 \le m \le 10^{10}$, $0 \le k \le 1000$. Translated by ChatGPT 5