Busy Beaver está tomando una clase de teoría de grafos, y su profesor le pide que cuente el número de grafos que satisfacen una condición especial. ¡Ayúdale a resolver el siguiente problema sobre conteo de grafos!
Sea $P$ un número primo impar y $N$ un entero positivo. Cuenta el número de grafos simples, etiquetados y no dirigidos con $NP$ vértices que no contienen ningún ciclo simple de longitud $P$. Calcula la respuesta módulo $P$. ¡Nota la repetición de $P$ en este enunciado!
Un ciclo simple en un grafo no dirigido es un ciclo que no utiliza ningún vértice más de una vez.
Entrada
La entrada consiste en una línea con dos enteros: $P$ ($3 \le P < 5000$) y $N$ ($1 \le N \le 10^9$). $P$ es un número primo impar.
Salida
Imprime un único entero módulo $P$.
Puntuación
- (25 puntos) $N \le P$ y $P \le 500$.
- (25 puntos) $N \le P$.
- (25 puntos) $P \le 500$.
- (25 puntos) Sin restricciones adicionales.
Ejemplos
Entrada 1
3 1
Salida 1
1
Entrada 2
5 4
Salida 2
1
Entrada 3
479 166
Salida 3
344
Nota
En el primer ejemplo, estamos contando el número de grafos etiquetados con $1 \cdot 3 = 3$ vértices que no tienen un ciclo simple de longitud 3. De los $2^3 = 8$ grafos totales, exactamente uno de ellos contiene un ciclo simple de longitud 3, por lo que hay un total de 7 formas. Luego, 7 módulo 3 es 1.