Busy Beaver ha dejado la programación y ha decidido dedicarse al arte moderno.
Busy Beaver tiene dos fichas con pintura. Él desea pintar un grafo no dirigido de la siguiente manera:
- Inicialmente, todos los vértices están sin pintar. Primero, Busy Beaver coloca una ficha en el vértice 1 y la otra en el vértice 2.
- Luego, desliza las fichas a lo largo de las aristas del grafo; siempre que un vértice sea cubierto por una ficha, ese vértice se pinta. (Nótese que los vértices 1 y 2 comienzan pintados).
- Si es posible pintar todos los vértices de tal manera que las dos fichas nunca estén conectadas por una arista en ningún momento durante el proceso, el grafo se denomina artístico.
Encuentre el número de grafos no dirigidos artísticos con $N$ vértices. Dado que la respuesta puede ser grande, imprímala módulo un número primo $P$.
Entrada
La única línea de cada caso de prueba contiene dos enteros $N$ y $P$ ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$). $P$ es un número primo.
Salida
Imprima el número de grafos no dirigidos artísticos con $N$ vértices, módulo $P$.
Ejemplos
Entrada 1
2 799999999
Salida 1
1
Entrada 2
3 998244853
Salida 2
2
Entrada 3
1984 998244853
Salida 3
424428556
Nota
En el primer caso de prueba, el grafo con dos vértices y sin aristas es el único grafo artístico.
En el segundo caso de prueba, los dos primeros grafos a continuación son artísticos. El último grafo no es artístico, porque es imposible llegar a pintar el vértice 3.
