Dla wszystkich drzew ukorzenionych o $n$ wierzchołkach, oblicz sumę wysokości wszystkich takich drzew. Wynik podaj modulo $p$.
Wysokość drzewa to długość najdłuższej ścieżki prostej wychodzącej z korzenia.
Dwa drzewa ukorzenione są równe wtedy i tylko wtedy, gdy mają tę samą liczbę dzieci korzenia, a odpowiadające sobie poddrzewa (licząc od lewej do prawej) są równe.
Wejście
Wczytaj dwie liczby całkowite $n, p$.
Wyjście
Wypisz sumę wysokości wszystkich drzew ukorzenionych o $n$ wierzchołkach modulo $p$.
Przykład
Przykład 1
Wejście
4 998244353
Wyjście
10
Uwagi
Dla przykładu 1:
- Istnieje $1$ drzewo o wysokości $1$: korzeń ma bezpośrednio $3$ dzieci.
- Istnieją $3$ drzewa o wysokości $2$:
- Jedno dziecko, które posiada dwoje dzieci.
- Dwoje dzieci, z których jedno jest liściem (liczymy to jako dwa przypadki, ponieważ dzieci są uporządkowane: pierwsze dziecko jest liściem lub drugie dziecko jest liściem).
- Istnieje $1$ drzewo o wysokości $3$: ścieżka (łańcuch).
Przykład 2
Wejście
10 998244353
Wyjście
19838
Przykład 3
Wejście
514 998244353
Wyjście
867876856
Podzadania
Dla pierwszych $20\%$ danych, $n\le 50$.
Dla pierwszych $40\%$ danych, $n\le 400$.
Dla pierwszych $60\%$ danych, $n\le 1000, p = 998244353$.
Dla pierwszych $80\%$ danych, $n\le 2000$.
Dla $100\%$ danych, $1\le n\le 10^5, 9\times 10^8 \le p\le 1.01 \times 10^9$, gdzie $p$ jest liczbą pierwszą.