#3113. Toy

题目描述

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

输入格式

输入N，M

3<=N<=10^9, 2<=M<=10^9

输出格式

输出方案数 Mod M的结果

样例

样例输入

3 10000  

4 10000  

4 10  

样例输出

6  

13  

3  

数据范围与提示