测试数据来自 system/1670

背景

出了道重题..有点不爽..就放了这道题

描述

令f(n)表示正N边形用对角线剖分成三角形的方法数。

给定N
求sigma(f(i))mod m

格式

输入格式

两个正整数N M(3<=n<=10^6 1<=m<=10^9且保证m分解质因数以后最多只有7个不同的素因子)

输出格式

一个数，如题意

样例1

样例输入1

5 1000

样例输出1

8

限制

各个测试点2s

提示

本题来自特别夏令营，感谢caima神牛。