Busy Beaver посещает курс по теории графов, и его преподаватель просит его подсчитать количество графов, удовлетворяющих особому условию. Помогите ему решить следующую задачу о подсчете графов!

Пусть $P$ — нечетное простое число, а $N$ — положительное целое число. Подсчитайте количество неориентированных помеченных простых графов с $NP$ вершинами, которые не содержат простых циклов длины $P$. Вычислите ответ по модулю $P$. Обратите внимание на повторение $P$ в этом условии!

Простой цикл в неориентированном графе — это цикл, в котором ни одна вершина не встречается более одного раза.

Входные данные

Входные данные содержат одну строку с двумя целыми числами: $P$ ($3 \le P < 5000$) и $N$ ($1 \le N \le 10^9$). $P$ — нечетное простое число.

Выходные данные

Выведите единственное целое число по модулю $P$.

Подзадачи

• (25 баллов) $N \le P$ и $P \le 500$.
• (25 баллов) $N \le P$.
• (25 баллов) $P \le 500$.
• (25 баллов) Дополнительные ограничения отсутствуют.

Примеры

Входные данные 1

3 1

Выходные данные 1

1

Примечание

В первом примере мы подсчитываем количество помеченных графов с $1 \cdot 3 = 3$ вершинами, которые не содержат простых циклов длины 3. Из общего числа $2^3 = 8$ графов ровно один содержит простой цикл длины 3, поэтому всего существует 7 способов. Затем, $7 \pmod 3$ равно 1.

Входные данные 2

5 4

Выходные данные 2

1

Входные данные 3

479 166

Выходные данные 3

344