Busy Beaver a abandonné la programmation et a décidé de se lancer dans l'art moderne !
Busy Beaver possède deux jetons recouverts de peinture. Il souhaite peindre un graphe non orienté comme suit :
- Initialement, tous les sommets ne sont pas peints. Tout d'abord, Busy Beaver place un jeton sur le sommet 1 et l'autre sur le sommet 2.
- Ensuite, il fait glisser les jetons le long des arêtes du graphe ; chaque fois qu'un sommet est recouvert par un jeton, ce sommet devient peint. (Notez que les sommets 1 et 2 sont peints dès le départ.)
- S'il est possible de peindre tous les sommets de telle sorte que les deux jetons ne soient jamais reliés par une arête à aucun moment du processus, le graphe est dit artistique.
Trouvez le nombre de graphes non orientés artistiques à $N$ sommets. Comme la réponse peut être grande, donnez-la modulo un nombre premier $P$.
Entrée
La seule ligne de chaque test contient deux entiers $N$ et $P$ ($2 \le N \le 5000$ ; $5 \cdot 10^8 < P < 10^9$). $P$ est un nombre premier.
Sortie
Affichez le nombre de graphes non orientés artistiques à $N$ sommets, modulo $P$.
Exemples
Entrée 1
2 799999999
Sortie 1
1
Entrée 2
3 998244853
Sortie 2
2
Entrée 3
1984 998244853
Sortie 3
424428556
Remarque
Dans le premier cas de test, le graphe à deux sommets sans arête est le seul graphe artistique.
Dans le second cas de test, les deux premiers graphes ci-dessous sont artistiques. Le dernier graphe n'est pas artistique, car il est impossible de peindre le sommet 3 sans que les jetons ne soient reliés par une arête.
