T570749 编号（piggy）

小 Y 和小 X 在不同的城市。这一天小 Y 打算乘飞机去找小 X，她已经到达了安检口。百无聊赖的她开始观察其了面前不停走动的队伍。 小 Y 给排在她前面的 $n$ 个人都分配了编号，使得它们构成一个 $1\sim n$ 的排列。 小 Y 喜欢连续的数字。她把一个排列分成几个子串，每一段都是上升的连续正整数，且子串是**极大**的。而这个排列的美丽值就是这几个子串长度的最大值。例如，排列 $756891234$ 的分割为 $1234$，$56$，$7$，$89$，长度最大为 $4$，因此该子串的美丽值为 $4$。 小 Y 想知道所有排列的美丽值之和。 因为答案可能很大，所以请将答案对 $mod$ 取模，模数在输入中给出。

第一行两个整数 $n,\operatorname{mod}$，代表排队的总人数和模数。

输出一个整数，代表所有排列的美丽值之和对 $\operatorname{mod}$ 取模的结果。

### 样例1解释： 无论如何只有一个排列 $1$，因此答案是 $1$。 ### 样例2解释： 以下每个排列后边的括号代表其美丽值。 $1 2(2)$，$2 1(1)$，答案为 $3$。 ### 样例3解释： $1 2 3(3)$，$1 3 2(1)$，$2 1 3(1)$，$2 3 1(2)$，$3 1 2(2)$，$3 2 1(1)$，答案为 $10$。 | 部分分 | $n$ | 分值 | | :-----: | :--------: | :--: | | 0 | $\le 8$ | 10 | | 1 | $\le 18$ | 10 | | 2 | $\le 51$ | 20 | | 3 | $\le 3000$ | 60 | 对于所有数据，保证 $10^8\le mod \le 10^9$ 且 $mod$ 为质数。 提示：本题时限为 std 九倍以上，但选手们还需程序的常数因子对运行时间所带来的影响。