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.