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.