题目描述

裁判选择了 $N$ 个问题，现在是给它们评分的时候了！

问题 $i$ 必须获得一个整数分数 $A_i$，范围从 $1$ 到 $N$（包含边界）。问题已经按照难度排序：必须满足 $A_1 \\le A_2 \\le \\ldots \\le A_N$。不同的问题可以有相同的分数。

作为一个ICPC粉丝，你希望解决更多问题的选手能够排名靠前。因此，对于任意一个 $k$ ($1 \\le k \\le N-1$)，你希望任意 $k$ 个问题的分数之和严格小于任意 $k+1$ 个问题的分数之和。

有多少种分配分数的方式？计算这个数值对给定的素数 $M$ 取模后的结果。

约束条件

• $2 \\leq N \\leq 5000$
• $9 \\times 10^8 < M < 10^9$
• $M$ 是素数。
• 所有输入值都是整数。

输入

输入通过标准输入给出，格式如下：

$N$ $M$

输出

打印出分配问题分数的方式数，对 $M$ 取模。

示例输入 1

2 998244353

示例输出 1

3

可能的分配方式为 $(1, 1)$、$(1, 2)$、$(2, 2)$。

示例输入 2

3 998244353

示例输出 2

7

可能的分配方式为 $(1, 1, 1)$、$(1, 2, 2)$、$(1, 3, 3)$、$(2, 2, 2)$、$(2, 2, 3)$、$(2, 3, 3)$、$(3, 3, 3)$。

示例输入 3

6 966666661

示例输出 3

66

示例输入 4

96 925309799

示例输出 4

83779