久莲 es una chica a la que le encanta divertirse.

Por fin han llegado las vacaciones de verano y 久莲 ha decidido invitar a sus amigos a nadar. Primero quiere delimitar una zona rectangular del mar frente a la playa privada de su familia para utilizarla como piscina. Sin embargo, el mar está lleno de peligros: en algunos lugares el agua es demasiado profunda y en otros hay medusas venenosas. Quiere que toda la zona que delimite sea segura.

Tras un análisis inicial, representa esta zona del mar mediante una cuadrícula rectangular cuya base mide $N$ metros y cuya altura es $1001$ metros. La base de la cuadrícula corresponde a la playa privada de su familia, y cada cuadrado de $1\times1$ representa una unidad de zona marina. Le ha pedido a su padre que mañana compruebe si cada cuadrado es seguro. Cuando tenga esa información, solo tendrá que delimitar la piscina que desea.

Su piscina ideal debe cumplir las tres condiciones siguientes:

• Debe ser segura: cada unidad de zona marina de la piscina debe ser segura.
• Debe ser rectangular: la piscina debe ser una subcuadrícula de $a\times b$ de la cuadrícula completa.
• Debe ser adyacente a la playa: el borde inferior de la piscina debe coincidir con el borde inferior de la cuadrícula.

Por ejemplo, para $N=5$, supongamos que el resultado de las mediciones es el siguiente. Como $1001$ es demasiado grande, solo se muestran las tres filas inferiores; todas las demás zonas son peligrosas.

Puede elegir la subzona de $1\times4$ de la fila inferior o la subzona de $3\times1$ de la tercera columna. Ten en cuenta que no puede elegir la subzona de $1\times5$ de la fila superior, porque no es adyacente a la playa.

Para que sus amigos se diviertan, quiere que la superficie de la piscina sea lo mayor posible. Por tanto, elegirá la subzona de $1\times4$ de la fila inferior como solución definitiva.

Aunque hasta mañana no sabrá si cada unidad de zona marina es segura, quiere empezar ya a estimar la superficie de su piscina. Tras una estimación sencilla, supone que cada unidad es segura con probabilidad $q$ y peligrosa con probabilidad $1-q$, de forma independiente. Quiere saber cuál es la probabilidad de que la mayor piscina que pueda elegir tenga una superficie exactamente igual a $K$.

Sin embargo, a 久莲 no le interesan las matemáticas, así que quiere que la ayudes a calcular ese valor.

Entrada

Los datos se leen del archivo pool.in.

La entrada es una línea con cuatro enteros positivos $N,K,x,y$, donde $1\le x<y<998244353$. El valor de $q$ es $\frac{x}{y}$.

Salida

La salida se escribe en el archivo pool.out.

Escribe una línea con un entero: la respuesta módulo $998244353$.

Es decir, si la respuesta expresada como fracción irreducible es $\frac{a}{b}$, donde $a,b$ son coprimos, escribe el entero $x$ que satisface $bx\equiv a\pmod{998244353}$ y $0\le x<998244353$. Se puede demostrar que ese entero $x$ es único.

Ejemplos

Entrada 1

10 5 1 2

Salida 1

342025319

Ejemplo 2

Consulta pool/pool2.in y pool/pool2.ans en el directorio de los participantes.

Ejemplo 3

Consulta pool/pool3.in y pool/pool3.ans en el directorio de los participantes.

Nota

$x^{p-1}\equiv1\pmod p$, donde $p$ es primo y $x\in[1,p)$.

Subtareas