Busy Beaver porzucił programowanie i postanowił zająć się sztuką nowoczesną!
Busy Beaver ma dwa żetony z farbą. Chciałby pomalować graf nieskierowany w następujący sposób:
- Początkowo wszystkie wierzchołki są niepomalowane. Najpierw Busy Beaver umieszcza jeden żeton na wierzchołku 1, a drugi na wierzchołku 2.
- Następnie przesuwa żetony wzdłuż krawędzi grafu; za każdym razem, gdy wierzchołek jest przykryty przez żeton, staje się on pomalowany. (Zauważ, że wierzchołki 1 i 2 są pomalowane od początku).
- Jeśli możliwe jest pomalowanie wszystkich wierzchołków w taki sposób, aby dwa żetony nigdy nie były połączone krawędzią w żadnym momencie procesu, graf nazywamy artystycznym.
Znajdź liczbę artystycznych grafów nieskierowanych o $N$ wierzchołkach. Ponieważ wynik może być duży, wypisz go modulo liczba pierwsza $P$.
Wejście
Jedyna linia każdego testu zawiera dwie liczby całkowite $N$ oraz $P$ ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$). $P$ jest liczbą pierwszą.
Wyjście
Wypisz liczbę artystycznych grafów nieskierowanych o $N$ wierzchołkach, modulo $P$.
Przykład
Wejście 1
2 799999999
Wyjście 1
1
Wejście 2
3 998244853
Wyjście 2
2
Wejście 3
1984 998244853
Wyjście 3
424428556
Uwagi
W pierwszym przypadku testowym graf o dwóch wierzchołkach bez krawędzi jest jedynym grafem artystycznym.
W drugim przypadku testowym pierwsze dwa grafy poniżej są artystyczne. Ostatni graf nie jest artystyczny, ponieważ niemożliwe jest pomalowanie wierzchołka 3.
