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 Specification

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

Output Specification

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 amod998244353$ and $0\le x<998244353$.

Input

10 5 1 2

Output

342025319

Hint

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

Constraints

Test case	$N$	$K$
1,2	$=1$	$\le 1000$
3	$\le 10$	$\le 8$
4		$\le 9$
5		$\le 10$
6	$\le 1000$	$\le 7$
7		$\le 8$
8		$\le 9$
9,10,11		$\le 100$
12,13,14		$\le 1000$
15,16	$\le {10}^9$	$\le 10$
17,18		$\le 100$
19,20		$\le 1000$