Aria Melody Rhyme Sum

A melody is a string consisting only of the characters A, B and C. A melody is called an aria if and only if it can be reduced to the empty string by repeatedly deleting one of the following subsequences (not necessarily contiguous):

• AB (an A preceding a B)
• CA (a C preceding an A)
• AAA
• CCB (two C's followed by a B)

For nonnegative integers p, q, r, the rhyme of a melody that contains a copies of A, b copies of B and c copies of C is defined as \[ p^a q^b r^c \] (with the convention that \(0^0=1\)).

You are given four positive integers: n, p, q, r. For each k with 1 ≤ k ≤ n, consider all arias (i.e. melodies which can eventually be reduced to the empty string using the allowed operations) of length k. Compute the sum of their rhymes modulo 998244353. That is, for each k from 1 to n, output

\[ S_k = \sum_{\substack{S \text{ is an aria} \\ |S|=k}} p^{(\# A)} q^{(\# B)} r^{(\# C)} \pmod{998244353}. \]

inputFormat

The input consists of a single line containing four space‐separated integers:

1. n — the maximum length of melodies to consider,
2. p, q, and r — the parameters for computing the rhyme.

outputFormat

Output n space‐separated integers. The k-th integer should be the sum (modulo 998244353) of the rhymes of all arias of length k.

sample

1 2 3 4

0

</p>