久莲 é uma rapariga que gosta de se divertir.

As férias de verão finalmente chegaram e 久莲 decidiu convidar os amigos para nadar. Pretende primeiro delimitar uma região retangular do mar junto à praia privada da sua família para usar como zona de natação. Porém, o mar tem vários perigos: alguns locais são demasiado profundos e noutros aparecem medusas venenosas. Quer que toda a região delimitada seja segura.

Depois de uma análise preliminar, representou a região como uma grelha retangular com base de $N$ metros e altura de $1001$ metros. A base da grelha corresponde à praia privada da família e cada quadrado de $1\times1$ representa uma unidade de área do mar. Pediu ao pai que amanhã verifique se cada quadrado é seguro. Depois de receber essa informação, só terá de delimitar a zona de natação pretendida.

A sua zona de natação ideal satisfaz três condições:

• Deve ser segura: todas as unidades de área do mar que a compõem devem ser seguras.
• Deve ser retangular: deve ser uma subgrelha de $a\times b$ da grelha completa.
• Deve ser adjacente à praia: a sua fronteira inferior deve coincidir com a fronteira inferior da grelha.

Por exemplo, para $N=5$, suponhamos que os resultados são os seguintes (como $1001$ é demasiado grande, mostram-se apenas as três linhas inferiores da grelha; toda a parte restante é perigosa).

Ela pode escolher a sub-região de $1\times4$ da linha inferior ou a sub-região de $3\times1$ da terceira coluna. Não pode escolher a sub-região de $1\times5$ da linha superior, pois esta não é adjacente à praia.

Para que os amigos se divirtam, quer que a área da zona de natação seja o maior possível. Assim, escolhe como plano final a sub-região de $1\times4$ da linha inferior.

Embora só amanhã saiba se cada unidade de área do mar é segura, quer começar já a estimar a área da sua zona de natação. Numa estimativa simples, supõe que cada unidade de área é, independentemente, segura com probabilidade $q$ e insegura com probabilidade $1-q$. Quer saber qual é a probabilidade de a maior zona de natação que pode escolher ter área exatamente $K$.

Porém, 久莲 não se interessa por matemática e pede-te que a ajudes a calcular esse valor.

Entrada

Leia os dados do ficheiro pool.in.

A entrada contém uma linha com quatro inteiros positivos $N,K,x,y$, em que $1\le x<y<998\,244\,353$. O valor de $q$ é $\frac xy$.

Saída

Escreva a saída no ficheiro pool.out.

Imprima uma linha com um inteiro que represente a resposta módulo $998\,244\,353$.

Isto é, supondo que a resposta na forma de fração irredutível é $\frac ab$, com $a$ e $b$ primos entre si, imprima o inteiro $x$ tal que $bx\equiv a\pmod{998\,244\,353}$ e $0\le x<998\,244\,353$. Pode demonstrar-se que este inteiro $x$ é único.

Exemplos

Entrada 1

10 5 1 2

Saída 1

342025319

Exemplo 2

Consulte pool/pool2.in e pool/pool2.ans no diretório do participante.

Exemplo 3

Consulte pool/pool3.in e pool/pool3.ans no diretório do participante.

Observações

$x^{p-1}\equiv1\pmod p$, em que $p$ é primo e $x\in[1,p)$.

Subtarefas