久莲 ist ein Mädchen, das gerne spielt.

Endlich sind die Sommerferien da. 久莲 beschließt, ihre Freunde zum Schwimmen einzuladen. Zunächst möchte sie vor dem Privatstrand ihrer Familie einen rechteckigen Meeresbereich als Schwimmbecken abgrenzen. Im Meer lauern jedoch allerlei Gefahren: An manchen Stellen ist das Wasser zu tief, an anderen gibt es giftige Quallen. Sie möchte, dass der gesamte abgegrenzte Meeresbereich sicher ist.

Nach einer ersten Analyse stellt sie diesen Meeresbereich als rechteckiges Gitter mit einer Grundseite von $N$ Metern und einer Höhe von $1001$ Metern dar. Die Unterkante des Gitters entspricht dem Privatstrand ihrer Familie. Jedes kleine Quadrat von $1\,\mathrm m\times1\,\mathrm m$ stellt eine Einheitsmeeresfläche dar. Sie hat ihren Vater gebeten, morgen für jedes kleine Quadrat festzustellen, ob es sicher ist. Sobald sie diese Informationen hat, muss sie nur noch das gewünschte Schwimmbecken abgrenzen.

Ihr ideales Schwimmbecken erfüllt die folgenden drei Bedingungen:

• Es muss sicher sein. Das heißt, jede Einheitsmeeresfläche im Schwimmbecken muss sicher sein.
• Es muss rechteckig sein. Das heißt, es muss ein Teilgitter der Größe $a\times b$ des gesamten Gitters sein.
• Es muss an den Strand grenzen. Das heißt, die Unterkante des Schwimmbeckens muss unmittelbar an der Unterkante des Gitters liegen.

Wenn beispielsweise $N=5$ ist und die Messungen das folgende Ergebnis liefern (da $1001$ zu groß ist, sind hier nur die untersten drei Zeilen des Gitters dargestellt; der übrige Bereich ist gefährlich):

Dann kann sie den Teilbereich der Größe $1\times4$ in der untersten Zeile oder den Teilbereich der Größe $3\times1$ in der dritten Spalte wählen. Beachte, dass sie den Teilbereich der Größe $1\times5$ in der obersten Zeile nicht wählen darf, weil dieser nicht an den Strand grenzt.

Damit ihre Freunde Spaß haben, möchte sie die Fläche des Schwimmbeckens möglichst groß machen. Daher wählt sie schließlich den Teilbereich der Größe $1\times4$ in der untersten Zeile.

Obwohl sie erst morgen erfahren wird, ob jede Einheitsmeeresfläche sicher ist, möchte sie schon jetzt die Größe ihres Schwimmbeckens abschätzen. Nach einer einfachen Schätzung nimmt sie an, dass jede Einheitsmeeresfläche unabhängig mit Wahrscheinlichkeit $q$ sicher und mit Wahrscheinlichkeit $1-q$ unsicher ist. Sie möchte wissen, mit welcher Wahrscheinlichkeit die Fläche des größten Schwimmbeckens, das sie wählen kann, genau $K$ beträgt.

Da 久莲 sich jedoch nicht für Mathematik interessiert, möchte sie, dass du ihr bei der Berechnung dieses Wertes hilfst.

Eingabe

Lies die Daten aus der Datei pool.in.

Die Eingabe besteht aus einer Zeile mit vier positiven ganzen Zahlen $N,K,x,y$, wobei $1\le x<y<998244353$. Es gilt $q=\frac{x}{y}$.

Ausgabe

Schreibe die Ausgabe in die Datei pool.out.

Gib eine Zeile mit einer ganzen Zahl aus, die den Wert der Antwort modulo $998244353$ angibt.

Sei die vollständig gekürzte Form der Antwort also $\frac{a}{b}$, wobei $a$ und $b$ teilerfremd sind. Gib die ganze Zahl $x$ aus, für die $bx\equiv a\pmod{998244353}$ und $0\le x<998244353$ gelten. Man kann beweisen, dass diese ganze Zahl $x$ eindeutig ist.

Beispiele

Eingabe 1

10 5 1 2

Ausgabe 1

342025319

Beispiel 2

Siehe pool/pool2.in und pool/pool2.ans im Teilnehmerverzeichnis.

Beispiel 3

Siehe pool/pool3.in und pool/pool3.ans im Teilnehmerverzeichnis.

Hinweis

Es gilt $x^{p-1}\equiv1\pmod p$, wobei $p$ eine Primzahl und $x\in[1,p)$ ist.

Teilaufgaben