Idziesz dalej i spotykasz starca w szacie koloru czarnego. Przed drzwiami obok leży ogromna piaskownica, a starzec rysuje na niej gałązką dziwne symbole.

Starzec mówi ci, że od młodości marzył o rozwiązaniu pewnego problemu, a teraz, gdy jest już u kresu życia, wydaje się, że odkrył jedynie rąbek tajemnicy.

Może powinienem przekazać je wam, mówi starzec.

Nie martw się, nie chcę cię zbytnio dręczyć, przynajmniej przygotowałem dla ciebie niezbędne narzędzia.

Dla liczby całkowitej dodatniej $\alpha$, rozważmy następujący ciąg $a$ o długości $\alpha n$:

• Dla każdego $k=1,\dots, n$, w ciągu $a$ występuje dokładnie $\alpha$ razy liczba $k$.
• Jeśli $i < j$ oraz $a_i = a_j$, to dla każdego $i < k < j$ zachodzi $a_k \geq a_i$.

Ciąg spełniający powyższe wymagania nazywamy permutacją rzędu $(n,\alpha)$.

Dany jest ciąg $P$ będący permutacją rzędu $(n_0,\alpha)$. Mając dane $n$ oraz $m$, oblicz, ile istnieje permutacji rzędu $(n,\alpha)$, które zawierają $P$ jako podciąg oraz spełniają warunek:

• Istnieje dokładnie $m$ indeksów $i$, dla których $a_i > a_{i+1}$.

Wynik należy podać modulo $998244353$.

Wejście

W pierwszej linii znajdują się cztery liczby całkowite $\alpha$, $n$, $m$, $n_0$.

W drugiej linii znajduje się $\alpha n_0$ liczb całkowitych dodatnich, które tworzą permutację rzędu $(n_0,\alpha)$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę ciągów spełniających warunki zadania.

Przykład

Wejście 1

1 4 2 2
2 1

Wyjście 1

7

Wejście 2

2 4 2 2
1 2 2 1

Wyjście 2

19

Podzadania

Dla $10\%$ danych wejściowych zachodzi $n \leq 2000$.

Dla kolejnych $10\%$ danych wejściowych zachodzi $\alpha = 1$ oraz $n_0=1$.

Dla kolejnych $30\%$ danych wejściowych zachodzi $\alpha = 1$.

Dla kolejnych $15\%$ danych wejściowych zachodzi $\alpha = 2$ oraz $n_0=1$.

Dla kolejnych $15\%$ danych wejściowych zachodzi $\alpha = 2$.

Dla $100\%$ danych wejściowych zachodzi $1\leq n \leq 2\times 10^5$, $0\leq m < n$, $1\leq n_0\leq n$ oraz $1\leq \alpha n_0 \leq 2\times 10^5$.

Wskazówki

Aby ułatwić zawodnikom operacje na formalnych szeregach potęgowych, udostępniamy szablon. Zawodnicy mogą z niego korzystać i opierać się na nim w zależności od swoich potrzeb, ale mogą również z niego nie korzystać.