Pool

There is a pool that can be modeled as a rectangular grid with width $N$ meters and height 1001 meters. The bottom edge of the grid corresponds to a beach. Each $1m \times 1m$ square cell of the grid represents a unit of sea.

A safe area for swimming shall satisfy the following constraints:

• All cells in the pool are safe.
• Must be rectangular.
• Must be adjacent to the bottom edge (i.e. the beach).

Given that each square cell of $1m \times 1m$ has probability $q$ to be safe (independently), and $1-q$ probability to be not safe, find the probability such that the largest safe area for swimming is exactly $K$.

Input a line with four positive integers $N,K,x,y$ where $1 \leq x < y < 998244353$. The parameter $q$ is just $\frac{x}{y}$.

Output a line with an integer denoting the answer modulo 998244353: if the answer is $\frac{a}{b}$ in reduced form (i.e. $a$ and $b$ are coprime), then output $x$ such that $bx \equiv a \bmod 998244353$ and $0 \leq x < 998244353$.

• $1 \leq N \leq 10^9$
• $1 \leq K \leq 1000$

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