Mamy $N$ pudełek, z których każde jest oznaczone liczbą całkowitą od $1$ do $N$. Ponadto dla każdej liczby całkowitej od $1$ do $N$ istnieje $M$ kul oznaczonych tą liczbą.
Te $NM$ kul jest tasowanych, a następnie rozdzielanych do $N$ pudełek, tak aby w każdym pudełku znalazło się dokładnie $M$ kul.
Istnieje $\frac{(NM)!}{(M!)^N}$ możliwych sposobów rozmieszczenia kul (przy założeniu, że wszystkie kule są rozróżnialne), a wszystkie te układy występują z jednakowym prawdopodobieństwem.
Wykonujesz operacje na tych pudełkach i kulach. Jedna operacja składa się z następujących kroków:
- Wybierz jedno pudełko i stań przed nim.
- Jeśli w tym pudełku nie ma żadnej kuli, zakończ operację.
- Wybierz dowolną kulę z tego pudełka i odrzuć ją poza pudełko.
- Na koniec stań przed pudełkiem, którego etykieta odpowiada etykiecie ostatnio odrzuconej kuli, i wróć do kroku 2.
Zdefiniuj swój wynik jako liczbę operacji wymaganych do usunięcia wszystkich $NM$ kul. Chcesz zminimalizować ten wynik.
Znajdź wartość oczekiwaną wyniku przy optymalnym działaniu, modulo 998244353.
Wejście
Pierwsza linia zawiera $N$ oraz $M$ w tej kolejności, oddzielone spacjami. ($1 \le N \le 10^5$, $1 \le M \le 100$)
Wyjście
Wypisz odpowiedź.
Przykład
Wejście 1
2 2
Wyjście 1
166374060
Wejście 2
3 1
Wyjście 2
831870296
Wejście 3
100000 100
Wyjście 3
402978825
Uwagi
Dla pierwszego przykładu możliwe układy kul i odpowiadające im optymalne sposoby działania są następujące:
Umieszczenie dwóch kul z etykietą 1 w pudełku 1 oraz dwóch kul z etykietą 2 w pudełku 2. (Prawdopodobieństwo 1/6)
- W pierwszej operacji stań przed pudełkiem 1. Stamtąd wyjmij kulę z etykietą 1 i stań przed pudełkiem 1. Następnie wyjmij kolejną kulę z etykietą 1 i ponownie stań przed pudełkiem 1. W tym momencie pudełko 1 jest puste, więc zakończ operację.
- W drugiej operacji stań przed pudełkiem 2. Stamtąd wyjmij kulę z etykietą 2 i stań przed pudełkiem 2. Następnie wyjmij kolejną kulę z etykietą 2 i ponownie stań przed pudełkiem 2. W tym momencie pudełko 2 jest puste, więc zakończ operację.
- W tym przypadku minimalny osiągalny wynik wynosi 2.
Umieszczenie jednej kuli z etykietą 1 i jednej kuli z etykietą 2 w każdym z pudełek 1 i 2. (Prawdopodobieństwo 2/3)
- W pierwszej operacji stań przed pudełkiem 1. Stamtąd wyjmij kulę z etykietą 1 i stań przed pudełkiem 1. Następnie wyjmij kulę z etykietą 2 i stań przed pudełkiem 2. Następnie wyjmij kulę z etykietą 2 i stań przed pudełkiem 2. Następnie wyjmij kulę z etykietą 1 i stań przed pudełkiem 1. W tym momencie pudełko 1 jest puste, więc zakończ operację.
- W tym przypadku minimalny osiągalny wynik wynosi 1.
Umieszczenie dwóch kul z etykietą 2 w pudełku 1 oraz dwóch kul z etykietą 1 w pudełku 2. (Prawdopodobieństwo 1/6)
- W pierwszej operacji stań przed pudełkiem 1. Stamtąd wyjmij kulę z etykietą 2 i stań przed pudełkiem 2. Następnie wyjmij kulę z etykietą 1 i stań przed pudełkiem 1. Następnie wyjmij kulę z etykietą 2 i stań przed pudełkiem 2. Następnie wyjmij kulę z etykietą 1 i stań przed pudełkiem 1. W tym momencie pudełko 1 jest puste, więc zakończ operację.
- W tym przypadku minimalny osiągalny wynik wynosi 1.
Podsumowując, minimalny wynik wynosi 2 z prawdopodobieństwem 1/6 oraz 1 z prawdopodobieństwem 5/6, więc oczekiwany wynik wynosi 7/6. Dlatego wypisujemy 166374060, co reprezentuje tę wartość modulo 998244353.
Definicja wartości oczekiwanej modulo 998244353
Można udowodnić, że poszukiwana wartość oczekiwana jest zawsze liczbą wymierną. Ponadto, przy ograniczeniach tego zadania, jeśli wartość oczekiwana zostanie zapisana jako nieskracalny ułamek $\frac{y}{x}$, gwarantuje się, że $x$ nie jest podzielne przez 998244353.
W takim przypadku istnieje unikalna liczba całkowita $z$ z przedziału od 0 do 998244352 włącznie, spełniająca $xz \equiv y \pmod{998244353}$. Wypisz to $z$.