Game on a Circle

Problem Description

There are $n$ stones on a circle, numbered from $1$ to $n$ in the clockwise direction such that the next of the $i$-th stone is the $(i + 1)$-th one $(i = 1, 2, \ldots, n - 1)$ and the next of the $n$-th stone is the first one. At the beginning of this game, all the stones exist. You will start from the first stone, and then repeatedly do the following operation until all the stones have been erased:

1. erase the current stone with probability $p$, and
2. move to the next stone that hasn't been erased in the clockwise direction. Now your task is, for $i = 1, 2, \ldots, n$, to calculate the probability that the $i$-th earliest erased stone is the $c$-th one. Due to the precision issue, you are asked to report the probabilities in modulo $998244353$ ($2^{23} \times 7 \times 17 + 1$, a prime). For example, if the irreducible fraction of some output value is $\frac{x}{y}$, then you are asked to output the minimum possible non-negative integer $z$ such that $x \equiv y z \pmod{998244353}$.

Input

There are several test cases. The first line contains an integer $T$ $(1 \leq T \leq 100)$, denoting the number of test cases. Then follow all the test cases. For each test case, the only line contains four integers $n$, $a$, $b$ and $c$ $(1 \leq c \leq n \leq 10^6, 0 < a < b < 998244353)$, representing that the number of stones is $n$, the probability $p$ is $\frac{a}{b}$ and the special stone is the $c$-th one. It is guaranteed that the sum of $n$ in all test cases is no larger than $10^6$. It is also guaranteed that $(1 - p)^i \not\equiv 1 \pmod{998244353}$ for $i = 1, 2, \ldots, n$ in each test case.

Output

For each test case, output $n$ lines, where the $i$-th line contains an integer, denoting the probability, in modulo $998244353$, that the $i$-th earliest erased stone is the $c$-th one.

Sample Input

2
3 1 2 2
4 1 3 3

Sample Output

713031681
570425345
713031681
706449850
560148451
952979832
775154927

Hint

For the first sample case, the irreducible fractions of the output values are [2/7, 3/7, 2/7]. For the second sample case, the irreducible fractions of the output values are [12/65, 356/1235, 333/1235, 318/1235].

Source

2020 Multi-University Training Contest 3