Jiulian is a girl who loves to play.

Summer vacation has finally arrived, and Jiulian has decided to invite her friends over for a swim. She plans to fence off a rectangular area of the sea outside her private beach to serve as a swimming pool. However, the ocean is full of various dangers; some places are too deep, and in some places, poisonous jellyfish appear. She wants the fenced-off area to be completely safe.

After a preliminary analysis, she has abstracted this sea area into a rectangular grid with a base of $N$ meters and a height of $1001$ meters. The base of the grid corresponds to her private beach, and each $1 \times 1$ small square represents a unit of the sea. She has asked her father to measure whether each small square is safe tomorrow. After obtaining this information, all she needs to do is fence off the swimming pool she wants.

The ideal swimming pool she has in mind satisfies the following three conditions: It must be safe. That is, every unit of the sea within the swimming pool must be safe. It must be a rectangle. That is, the swimming pool must be an $a \times b$ subgrid within the entire grid. * It must be adjacent to the beach. That is, the bottom boundary of the swimming pool must be flush with the bottom boundary of the grid.

For example, when $N = 5$, if the measurement results are as follows (since $1001$ is too large, only the information for the bottom three rows of the grid is shown here, and all other parts are dangerous):

She can choose the $1 \times 4$ sub-sea area in the bottom row, or she can choose the $3 \times 1$ sub-sea area in the third column. Note that she cannot choose the $1 \times 5$ sub-sea area in the top row because it is not adjacent to the beach.

To ensure her friends have a good time, she wants the area of the swimming pool to be as large as possible. Therefore, she will choose the $1 \times 4$ sub-sea area in the bottom row as her final plan.

Although she will only know whether each unit of the sea is safe tomorrow, she wants to take action now to estimate how large her swimming pool area will be. Based on a simple estimate, she assumes that each unit of the sea has an independent probability $q$ of being safe, and a probability $1 - q$ of being unsafe. She wants to know the probability that the maximum area of the swimming pool she can choose is exactly $K$.

However, Jiulian is not interested in mathematics, so she wants you to help her calculate this value.

Input

The input consists of a single line containing four positive integers $N, K, x, y$, where $1 \le x < y < 998244353$. The value of $q$ is $\frac{x}{y}$.

Output

Output a single integer representing the value of the answer modulo $998244353$.

That is, if the answer is expressed as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are coprime, output the integer $x$ such that $bx \equiv a \pmod{998244353}$ and $0 \le x < 998244353$. It can be proven that such an integer $x$ is unique.

Examples

Input 1

10 5 1 2

Output 1

342025319

Input 2

pool/pool2.in

Output 2

pool/pool2.ans

Input 3

pool/pool3.in

Output 3

pool/pool3.ans

Note

$x^{p-1} \equiv 1 \pmod p$, where $p$ is a prime number and $x \in [1, p)$.

Subtasks