Description

蓝桥杯 C++青少组的比赛有 n 个问题，现在请你给这 n 个问题分配分值。 n 个问题已经按从简单到困难排好序，第i 个问题的分值是 Ai。n 个问题的分值满足如下关系： 1≤A1≤A2≤…≤An≤n。不同的问题可以具有相同的分值。 主办方希望：解决更多问题的参赛者的排名更高。 因此，对于任何解决了k（1≤k≤n-1）个问题的参赛者，其分数总和一定要小于解决了任何 k + 1 个问题的参赛者的分数总和。

你有几种分配分值的方法？ 将答案对素数 m 取余后输出。

Input Format

整数 n 和 m 其中 2≤n≤5000,9×108<m<109 ，m 为素数。

Output Format

分值分配的方案数对 m 取余后的数字。

2 998244353

3

3 998244353

7

Hint

样例输入 1： 2 998244353 样例输出 1： 3 样例 1 说明： 2 个题的分值分配有 3 种方案： (1,1), (1,2), (2,2)。 样例输入 2： 3 998244353 样例输出 2： 7 样例 2 说明： 3 个题的分值分配有 7 种方案：(1,1,1), (1,2,2), (1,3,3), (2,2,2), (2,2,3), (2,3,3), (3,3,3)。

Source

第十一届蓝桥青少组省赛C++高级组