Busy Beaver uczęszcza na zajęcia z teorii grafów, a jego nauczyciel poprosił go o policzenie liczby grafów, które spełniają specjalny warunek. Pomóż mu rozwiązać poniższy problem dotyczący zliczania grafów!

Niech $P$ będzie nieparzystą liczbą pierwszą, a $N$ dodatnią liczbą całkowitą. Oblicz liczbę nieskierowanych, etykietowanych grafów prostych o $N \cdot P$ wierzchołkach, które nie zawierają żadnego prostego cyklu o długości $P$. Wynik podaj modulo $P$. Zwróć uwagę na powtórzenie $P$ w treści zadania!

Prosty cykl w grafie nieskierowanym to cykl, który nie odwiedza żadnego wierzchołka więcej niż raz.

Wejście

Wejście składa się z jednej linii zawierającej dwie liczby całkowite: $P$ ($3 \le P < 5000$) oraz $N$ ($1 \le N \le 10^9$). $P$ jest nieparzystą liczbą pierwszą.

Wyjście

Wypisz pojedynczą liczbę całkowitą modulo $P$.

Punktacja

• (25 punktów) $N \le P$ oraz $P \le 500$.
• (25 punktów) $N \le P$.
• (25 punktów) $P \le 500$.
• (25 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3 1

Wyjście 1

1

Wejście 2

5 4

Wyjście 2

1

Wejście 3

479 166

Wyjście 3

344

Uwagi

W pierwszym przykładzie zliczamy liczbę etykietowanych grafów o $1 \cdot 3 = 3$ wierzchołkach, które nie posiadają prostego cyklu o długości 3. Spośród wszystkich $2^3 = 8$ możliwych grafów, dokładnie jeden zawiera prosty cykl o długości 3, więc istnieje łącznie 7 sposobów. Następnie, 7 modulo 3 wynosi 1.