久莲 jest dziewczynką, która lubi się bawić.

Wreszcie nadeszły wakacje. 久莲 postanowiła zaprosić przyjaciół do pływania. Najpierw chce wyznaczyć prostokątny obszar morza przy swojej prywatnej plaży jako kąpielisko. Jednak w morzu czyhają różne niebezpieczeństwa: miejscami woda jest zbyt głęboka, a gdzie indziej występują jadowite meduzy. Chce, aby cały wyznaczony obszar był bezpieczny.

Po wstępnej analizie przedstawiła ten obszar jako prostokątną siatkę o podstawie długości $N$ metrów i wysokości $1001$ metrów. Dolny bok siatki odpowiada jej prywatnej plaży, a każdy kwadrat o wymiarach $1\times1$ reprezentuje jednostkowy obszar morza. Poprosiła tatę, aby jutro sprawdził bezpieczeństwo każdego kwadratu. Gdy otrzyma te informacje, pozostanie jej wyznaczyć wymarzone kąpielisko.

Jej idealne kąpielisko spełnia trzy warunki:

• Musi być bezpieczne: każdy jednostkowy obszar morza należący do kąpieliska jest bezpieczny.
• Musi być prostokątne: jest podsiatką całej siatki o wymiarach $a\times b$.
• Musi przylegać do plaży: dolna krawędź kąpieliska musi stykać się z dolną krawędzią siatki.

Na przykład dla $N=5$ wyniki pomiarów mogą wyglądać następująco (ponieważ $1001$ to zbyt duża wysokość, pokazano tylko trzy najniższe wiersze siatki; pozostała część jest niebezpieczna):

Może wtedy wybrać obszar $1\times4$ w najniższym wierszu albo obszar $3\times1$ w trzeciej kolumnie. Nie może jednak wybrać obszaru $1\times5$ w najwyższym wierszu, ponieważ nie przylega on do plaży.

Aby przyjaciele dobrze się bawili, chce, by kąpielisko miało jak największą powierzchnię. Dlatego jako ostateczne rozwiązanie wybierze obszar $1\times4$ w najniższym wierszu.

Choć dopiero jutro dowie się, czy poszczególne jednostkowe obszary są bezpieczne, już teraz chciałaby oszacować powierzchnię kąpieliska. Na podstawie prostych szacunków zakłada, że każdy jednostkowy obszar jest niezależnie bezpieczny z prawdopodobieństwem $q$, a niebezpieczny z prawdopodobieństwem $1-q$. Chce wiedzieć, jakie jest prawdopodobieństwo, że największe kąpielisko, które może wybrać, będzie miało powierzchnię dokładnie $K$.

久莲 nie interesuje się jednak matematyką, więc prosi cię o obliczenie tej wartości.

Wejście

Dane należy odczytać z pliku pool.in.

Jedyny wiersz zawiera cztery dodatnie liczby całkowite $N,K,x,y$, gdzie $1\le x<y<998244353$. Wartość $q$ wynosi $\frac{x}{y}$.

Wyjście

Wynik należy zapisać do pliku pool.out.

Wypisz jeden wiersz z jedną liczbą całkowitą, będącą odpowiedzią modulo $998244353$.

Dokładniej, niech odpowiedź po skróceniu do ułamka nieskracalnego ma postać $\frac{a}{b}$, gdzie $a$ i $b$ są względnie pierwsze. Wypisz liczbę całkowitą $x$, dla której $bx\equiv a\pmod{998244353}$ oraz $0\le x<998244353$. Można udowodnić, że taka liczba całkowita $x$ jest jednoznacznie wyznaczona.

Przykład

Wejście 1

10 5 1 2

Wyjście 1

342025319

Przykład 2

Zobacz pliki pool/pool2.in i pool/pool2.ans w katalogu zawodnika.

Przykład 3

Zobacz pliki pool/pool3.in i pool/pool3.ans w katalogu zawodnika.

Uwagi

$x^{p-1}\equiv1\pmod p$, gdzie $p$ jest liczbą pierwszą, a $x\in[1,p)$.

Podzadania