题目描述

外面有一圈 $n$ 个结点，中心有一个结点与 $n$ 个结点都相连，总共就是 $2\times n$ 条边，删除 $n$ 条边，使 $n+1$ 个点连通，旋转相同视为等价，问有多少种情况。

输入格式

输入$n,m$。

输出格式

输出方案数 $\mod m$ 的结果

3 100004 100004 10

6133

数据规模与约定

对于 $100\%$ 的数据，$3\le n\le 10^9$，$2\le m \le 10^9$。