配置

20组数据,传统型,没有SpecialJudge。

背景

萌萌哥哥家里养了很多盆植物,其中有一盆仙人掌吸引了tangjz。

描述

tangjz发现了一盆仙人掌,正准备使用计算机三维画图软件画一幅仙人掌图。

我们可以将一颗仙人掌的轮廓抽象成n个不同的点(不妨编号1~n)与许多边,那么这n个点就组成了一个无向连通图!

因为仙人掌总是一瓣一瓣的,不会有两瓣有重合部分,这意味着图中任意一条边至多只出现在一条简单回路里。

如果只告诉你n是多少,你能猜出来tangjz可以画多少种不同的仙人掌吗?

这里的不同是指,两幅图不能在经过一定的空间翻转后重合。

由于答案可能很大,你只需要算出答案对k取模的值即可。

输入格式

两个用空格隔开的正整数n和k,含义见描述。

输出格式

一行输出,即答案对k取模的值。

样例输入1

4 32

样例输出1

31

样例解释1

样例输入输出2

比赛数据包\plant\plant.in和plant.out

数据范围与约定

  • 对于10%的数据:n\leq 10
  • 对于30%的数据:n\leq 50
  • 对于100%的数据:n\leq 200,2\leq k\leq 1000000