#3113. Toy

内存限制:128 MiB 时间限制:1 Sec

题目描述

外面有一圈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

数据范围与提示