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.