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 \leq 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 a \bmod 998244353~ and ~0 \leq x < 998244353~.

Input

10 5 1 2

Output

342025319

Hint

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

Constraints

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