Ejercicio.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem types
Allowed languages
C, C++, Java, Pascal, Python, VB

El granjero John ha ideado una nueva rutina de ejercicios matutinos para las vacas (otra vez).

Como antes, las N vacas (1 \leq N \leq 10^4) están en fila. La vaca i-ésima de la izquierda tiene la etiqueta i para cada 1 \leq i \leq N. Les dice que repitan el siguiente paso hasta que las vacas estén en el mismo orden que cuando empezaron:

\bull Dada una permutación A de longitud N, las vacas cambian su orden de forma que la i-ésima vaca de la izquierda antes del cambio es la A_i-sima de la izquierda después del cambio.

Por ejemplo, si A = (1,2,3,4,5) entonces las vacas realizan un paso. Si A = (2,3,1,5,4) entonces las vacas realizan seis pasos. El orden de las vacas de izquierda a derecha después de cada paso es el siguiente:

\bull 0 pasos: (1,2,3,4,5)

\bull 1 paso: (3,1,2,5,4)

\bull 2 pasos: (2,3,1,4,5)

\bull 3 pasos: (1,2,3,5,4)

\bull 4 pasos: (3,1,2,4,5)

\bull 5 pasos: (2,3,1,5,4)

\bull 6 pasos: (1,2,3,4,5)

Encuentra la suma de todos los enteros positivos K tal que exista una permutación de longitud N que requiera que las vacas ejecuten exactamente K pasos.

Como este número puede ser muy grande, obtenga la respuesta en módulo M(10^8 \leq M \leq 10^9 + 7, M es primo).

Entrada

La primera línea contiene N y M.

Salida

Un único número entero.

Ejemplo de Entrada

5 1000000007

Ejemplo de Salida

21

Existen permutaciones que hacen que las vacas tomen 1, 2, 3, 4, 5 y 6 pasos. Por tanto, la respuesta es 1+2+3+4+5+6=21.

Restricciones

\bull Los casos de prueba 2-5 satisfacen N \leq 10^2.

\bull Los casos de prueba 6-10 no satisfacen ninguna restricción adicional.


Comments