P7102 [W1] Calculation

There is an $m$-term polynomial $p(x)$ and two parameters $c$ and $t$, where $p(x)=a_0+a_1x+\dots+a_{m-1}x^{m-1}$. Define a new function $s(n)$: $$s(n)=\sum_{i=1}^np(i)[\gcd(i,n)=1]\bmod 998244353$$ Please compute $s(c),s(c^2),\dots,s(c^t)$.

The first line contains three positive integers $m,c,t$. The second line contains $m$ positive integers $a_0,a_1,\dots,a_{m-1}$.

Output $t$ lines. The $i$-th line contains one positive integer $s(c^i)$.

For $10\%$ of the testdata, $t\le2,c\le100$. For $30\%$ of the testdata, $t\le1000,m\le1000$. For $50\%$ of the testdata, $t\le5\cdot10^4,m\le5\cdot10^4,c\le10^{12}$. For another $10\%$ of the testdata, $c=123456789$. For all testdata, $1\le t\le2\cdot10^5,1\le m\le2\cdot10^5,1\le c\le10^{18}$. Translated by ChatGPT 5