410307: GYM104008 D Alice's Dolls
Description
Alice Margatroid is a skilled magician living in the Forest of Magic, who is good at making and controlling dolls. Today she is selling her self-made dolls to earn some money.
To attract people, Alice does not sell her dolls directly. Instead, she made a sweepstake (lottery) with different types of dolls. For each draw, the customer will get a special doll with a fixed probability $$$\frac a b$$$, a rational number within $$$(0, 1]$$$ (including $$$1$$$ but not $$$0$$$). Otherwise, the customer will get a doll of the usual kind.
By coincidence, Cirno goes to the Forest of Magic today. She finds the special dolls very attractive, but the usual dolls are not. Cirno decides to keep drawing until she gets $$$n$$$ special dolls, but she does not have much money, so she wants to estimate how many times she needs to draw.
Given a non-negative integer $$$m$$$, suppose the times Cirno needs to draw is $$$x$$$. For each non-negative integer $$$k$$$ between $$$0$$$ and $$$m$$$ (both inclusive), Cirno wants to know the expected value of $$$x^k$$$. The answers can be proven to be rational numbers, and you only need to output the answers modulo $$$998\,244\,353$$$, which is a prime number.
The value of a rational number $$$r$$$ modulo a prime $$$p$$$ is defined as follows: suppose $$$r = \frac x y$$$, where $$$x$$$ and $$$y$$$ are non-negative integers, and $$$0 \le x < p$$$, $$$1 \le y < p$$$. Also suppose there is a non-negative integer $$$z \in [0, p - 1]$$$ such that $$$yz \equiv 1 \pmod p$$$, then $$$r \equiv x z \pmod p$$$, in other words, the value of $$$r \bmod p$$$ is equal to $$$xz \bmod p$$$. It can be proven that there is a unique $$$z \in [0, p - 1]$$$ for each $$$y$$$, so the value is surely determined.
InputThe only line of input contains four integers $$$n$$$ ($$$1 \le n \le 10^5$$$), $$$m$$$ ($$$0 \le m \le 10^5$$$), $$$a$$$, $$$b$$$ ($$$1 \le a \le b \le 998\,244\,352$$$), indicating that Cirno wants to get $$$n$$$ special dolls, and the upper bound of $$$k$$$ is $$$m$$$ (inclusive), and the probatility to get a special doll in a single draw is $$$\frac a b$$$.
OutputOutput $$$m + 1$$$ integers separated with line breaks, the $$$i$$$-th ($$$0 \le i \le m$$$) of which represents the value of the expectation of $$$x^i$$$ modulo $$$998\,244\,353$$$.
ExamplesInput1 3 1 2Output
1 2 6 26Input
100 5 1 6Output
1 600 363000 221433000 425510992 941092730