El profesor de matemáticas de IslaInformatiza escribió algunas secuencias en la pizarra, cada una con ~N~ números diferentes, todos del ~1~ al ~N~, y les dijo a los estudiantes que estas secuencias tenían alguna propiedad especial. Después de un rato, uno de los estudiantes, Deni, adivinó la propiedad correcta. Todas las secuencias en la pizarra tenían al menos un par de números adyacentes en la forma ~(x,x+1)~. Deni estaba tan feliz que calificó de bonita este tipo de secuencia.

Por ejemplo, para ~N=4~ las secuencias: ~3,1,2,4~ y ~2,3,4,1~ son bonitas pero las secuencias ~2,4,1,3~ y ~4,3,2,1~ no lo son. Después de eso, el profesor de matemáticas le dió a Deni una pregunta más difícil. Le pidió que calculara el número de todas las secuencias bonitas posibles con ~N~ números diferentes, todos del ~1~ al ~N~. Esto fue tan difícil que Deni no pudo encontrar una respuesta durante toda la clase. Eres amigo de Deni y quieres ayudarlo.

Escribe el programa, que para un ~N~ dado tiene que decirle a Deni el número de secuencias bonitas. Este número puede ser bastante grande, por lo que hay que calcularlo en módulo ~M~.

Entrada

En la primera línea de la entrada estándar, lea dos números enteros ~N~ y ~M~: la longitud de las secuencias en la pizarra y el módulo utilizadas para el cálculo.

Salida

En una línea de la salida estándar, el programa tiene que escribir un número entero: el número de secuencias bonitas con ~N~ números diferentes, todos del ~1~ al ~N~ , módulo ~M~.

Restricciones

• ~1 \leq N \leq 10^{18}~
• ~2 \leq M \leq 10^7~

Ejemplo #1 de Entrada

4 42

Ejemplo #1 de Salida

13

Explicación del Ejemplo: Las secuencias bonitas con 4 números diferentes, todos del 1 al 4, son:

1 2 3 4 
1 2 4 3 
1 3 4 2 
1 4 2 3 
2 1 3 4 
2 3 1 4
2 3 4 1 
3 1 2 4
3 4 1 2
3 4 2 1
4 1 2 3
4 2 3 1
4 3 1 2

Ejemplo #2 de Entrada

2000 10009

Ejemplo #2 de Salida

1295