Ejercicio.
El granjero John ha ideado una nueva rutina de ejercicios matutinos para las vacas (otra vez).
Como antes, las vacas están en fila. La vaca -ésima de la izquierda tiene la etiqueta para cada . Les dice que repitan el siguiente paso hasta que las vacas estén en el mismo orden que cuando empezaron:
Dada una permutación de longitud , las vacas cambian su orden de forma que la -ésima vaca de la izquierda antes del cambio es la -sima de la izquierda después del cambio.
Por ejemplo, si entonces las vacas realizan un paso. Si entonces las vacas realizan seis pasos. El orden de las vacas de izquierda a derecha después de cada paso es el siguiente:
pasos:
paso:
pasos:
pasos:
pasos:
pasos:
pasos:
Encuentra la suma de todos los enteros positivos tal que exista una permutación de longitud que requiera que las vacas ejecuten exactamente pasos.
Como este número puede ser muy grande, obtenga la respuesta en módulo es primo.
Entrada
La primera línea contiene y .
Salida
Un único número entero.
Ejemplo de Entrada
5 1000000007
Ejemplo de Salida
21
Existen permutaciones que hacen que las vacas tomen y pasos. Por tanto, la respuesta es .
Restricciones
Los casos de prueba satisfacen .
Los casos de prueba no satisfacen ninguna restricción adicional.
Comments
No entiendo la permutación, alguien me podría explicar.