【题目描述】

Chris 要生成一张含有 n 个点的有向图。她要求：

1.若有 a->b 的边，则有 b->a 的边；

2.若有 a->b 的边和 b->c 的边，则有 a->c 的边；（a 和 c 可以是同一个点）

3.至少有一个点没有自环。

问：Chris 能得到多少个不同的有向图？结果对 m 取模。

【输入格式】

一行两个整数 n，m。

【输出格式】

一行一个数，即答案。

【样例输入】

2 5

【样例输出】

3

【样例解释】

三种方案分别是：

（1）没有边；

（2）只有一条 1 到 1 的边；

（3）只有一条 2 到 2 的边。

【数据规模与约定】

10%的数据，n≤6

30%的数据，n≤15

60%的数据，n≤100

100%的数据，n≤2000, 2≤m≤1,000,000,007