Infinite Series Summation with a Polynomial

Given a polynomial \(f(n)=a_0+a_1n+\cdots+a_dn^d\) and a rational number \(r\) such that \(0<r<1\) (represented as \(r=\frac{A}{B}\)), compute the infinite sum

\[ S=\sum_{n=0}^{\infty} f(n)\,r^n \;=\; \sum_{n=0}^{\infty} \Bigl(a_0+a_1n+\cdots+a_dn^d\Bigr) r^n, \]

It can be shown that the answer can be written in its simplest form as \(\frac{p}{q}\). You are only required to output

\[ p\times q^{-1} \ \bmod\ 998244353, \]

where \(q^{-1}\) is the modular inverse of \(q\) modulo \(998244353\).

Hint: Use generating functions. In particular, note that for any nonnegative integer \(k\), \[ \sum_{n\ge0} n^k x^n = \frac{P_k(x)}{(1-x)^{k+1}}, \] where \(P_k(x)\) is a polynomial of degree at most \(k\). One can compute \(P_k(x)\) using Stirling numbers of the second kind.

inputFormat

The input consists of three lines:

1. An integer \(d\) \( (0 \le d)\) representing the degree of the polynomial \(f(n)\).
2. \(d+1\) space-separated integers \(a_0, a_1, \ldots, a_d\) representing the coefficients of \(f(n) = a_0 + a_1 n + \cdots + a_d n^d\).
3. Two space-separated integers \(A\) and \(B\) representing the rational number \(r = \frac{A}{B}\) (with \(0 < \frac{A}{B} < 1\)).

outputFormat

Output a single integer which is \(p\times q^{-1}\ \bmod\ 998244353\), where \(\frac{p}{q}\) is the answer in its simplest form.

sample

0
1
1 2

2

</p>