Polynomial GCD Sum Query

We are given a polynomial \(p(x)=a_0+a_1x+\cdots+a_{m-1}x^{m-1}\) with \(m\) terms and two parameters \(c\) and \(t\). Define the function \(s(n)\) by

\[ s(n)=\sum_{i=1}^{n} p(i)\cdot[\gcd(i,n)=1] \bmod 998244353, \]

where the indicator function \([\gcd(i,n)=1]\) equals 1 if \(\gcd(i,n)=1\) and 0 otherwise. The task is to compute \(s(c),\ s(c^2),\dots, s(c^t)\).

Note: The modulo is taken with respect to \(998244353\).

inputFormat

The input consists of three lines:

• The first line contains an integer \(m\), the number of coefficients.
• The second line contains \(m\) space-separated integers \(a_0,a_1,\dots,a_{m-1}\), the coefficients of \(p(x)\).
• The third line contains two integers \(c\) and \(t\) separated by space.

outputFormat

Output \(t\) integers: \(s(c), s(c^2), \dots, s(c^t)\) modulo \(998244353\), separated by spaces.

sample

2
1 1
2 2

2 6