Busy Beaver suit un cours de théorie des graphes, et son professeur lui demande de compter le nombre de graphes qui satisfont une condition particulière. Aidez-le à résoudre le problème suivant concernant le dénombrement de graphes !

Soit $P$ un nombre premier impair et $N$ un entier positif. Comptez le nombre de graphes simples, étiquetés et non orientés à $NP$ sommets qui ne contiennent aucun cycle simple de longueur $P$. Calculez la réponse modulo $P$.

Un cycle simple dans un graphe non orienté est un cycle qui n'utilise aucun sommet plus d'une fois.

Entrée

L'entrée consiste en une ligne contenant deux entiers : $P$ ($3 \le P < 5000$) et $N$ ($1 \le N \le 10^9$). $P$ est un nombre premier impair.

Sortie

Affichez un seul entier modulo $P$.

Barème

• (25 points) $N \le P$ et $P \le 500$.
• (25 points) $N \le P$.
• (25 points) $P \le 500$.
• (25 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

3 1

Sortie 1

1

Entrée 2

5 4

Sortie 2

1

Entrée 3

479 166

Sortie 3

344

Remarque

Dans le premier exemple, nous comptons le nombre de graphes étiquetés à $1 \cdot 3 = 3$ sommets qui n'ont pas de cycle simple de longueur 3. Parmi les $2^3 = 8$ graphes au total, un seul contient un cycle simple de longueur 3, il y a donc $8 - 1 = 7$ graphes qui n'en contiennent pas. Ensuite, 7 modulo 3 vaut 1.