Alice Margatroid 是一位居住在魔法森林的熟练魔术师，擅长制作和操控人偶。今天，她正在出售自己制作的人偶来赚取一些钱。

为了吸引顾客，Alice 并没有直接出售她的人偶。相反，她举办了一场有不同种类人偶的抽奖活动。在每次抽奖中，顾客将以固定的概率 $\frac{a}{b}$ 获得一个特殊人偶，这是一个 $(0, 1]$ 之间的有理数（包含 1 但不包含 0）。否则，顾客将获得一个普通人偶。

巧合的是，琪露诺今天去了魔法森林。她发现特殊人偶非常有吸引力，但普通人偶则不然。琪露诺决定一直抽奖直到她获得 $n$ 个特殊人偶，但她没有太多钱，所以她想估算她需要抽奖多少次。

给定一个非负整数 $m$，假设琪露诺需要抽奖的次数为 $x$。对于 $0$ 到 $m$ 之间的每个非负整数 $k$（包含 $0$ 和 $m$），琪露诺想知道 $x^k$ 的期望值。可以证明这些答案是有理数，你只需要输出这些答案对 $998\,244\,353$ 取模的结果，这是一个质数。

有理数 $r$ 对质数 $p$ 取模的值定义如下：假设 $r = \frac{x}{y}$，其中 $x$ 和 $y$ 是非负整数，且 $0 \le x < p$，$1 \le y < p$。同时假设存在一个非负整数 $z \in [0, p - 1]$ 使得 $yz \equiv 1 \pmod p$，那么 $r \equiv xz \pmod p$，换句话说，$r \pmod p$ 的值等于 $xz \pmod p$。可以证明对于每个 $y$，都存在唯一的 $z \in [0, p - 1]$，因此该值是唯一确定的。

输入格式

输入仅一行，包含四个整数 $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$)，表示琪露诺想要获得 $n$ 个特殊人偶，$k$ 的上限为 $m$（包含），以及单次抽奖获得特殊人偶的概率为 $\frac{a}{b}$。

输出格式

输出 $m + 1$ 个整数，以换行符分隔，其中第 $i$ 个（$0 \le i \le m$）表示 $x^i$ 的期望值对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

1 3 1 2

样例输出 1

1
2
6
26

样例输入 2

100 5 1 6

样例输出 2

1
600
363000
221433000
425510992
941092730