TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2835
  • 問題
  • P2835光之大陆
    制限 : 時間制限 : 10000 MS   メモリ制限 : 565536 KB
    問題説明

    在光之大陆的土地上,各种势力盘根错节。来自光之峡谷的精灵,来自黑暗森林的亡灵,来自古老东方的人类共同生活在一起。善于打造装置的矮人,善于发明的侏儒,隐匿于山林的巨人也坚守着属于自己的领土。这些种族之间关系错综复杂,构成了极其庞大的关系网络。大魔法师小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

    ヒント

    10%测试点保证 n=6
    30%测试点保证 n<=50
    100%测试点保证 n<=200,m<=1000000


    ソース  湖南省,感谢nodgd放题