6873: BZOJ2873：光之大陆

在光之大陆的土地上，各种势力盘根错节。来自光之峡谷的精灵，来自黑暗森林的亡灵，来自古老东方的人类共同生活在一起。善于打造装置的矮人，善于发明的侏儒，隐匿于山林的巨人也坚守着属于自己的领土。这些种族之间关系错综复杂，构成了极其庞大的关系网络。大魔法师小P想要研究其中的种族关系。 两个物种之间可以是盟友，也可以不是盟友，如果a1,a2..an满足ai和ai+1是盟友，且an和a1是盟友，则他们构成了一个联盟。 由于光之大陆正处于微妙的和平之中。所以一个合理的物种关系应满足如下条件: 1、对于任意两个物种A,B,都存在一个序列A,a1,a2..an,B,使得任意相邻两个种族是盟友(注意A,B不一定是盟友)。 2、对于任意两个联盟Sa,Sb,都不存在一个物种既参加了联盟Sa，又参加了联盟Sb。 小P想知道，大陆上的N个种族一共有多少种可能的结盟关系，由于结果可能很大，你只需要输出答案mod M的值。  

输入格式

一行两个正整数：N,M（含义如题所述）

输出格式

一个整数：ans表示方案mod M的值

样例输入

4 1000000

样例输出

31

提示

100%测试点保证 n <= 200, m <= 1000000

题目来源

没有写明来源