题目描述

在比赛中，评委选出了 $N$ 道题目，现在需要为每道题目分配分数。

第 $i$ 道题目的分数 $A_i$ 必须是 $1$ 到 $N$ 之间的整数。此外，题目已经按照难度从易到难排列，要求 $A_1 \leq A_2 \leq \ldots \leq A_N$（允许多道题目的分数相同）。

你是 ICPC 的粉丝，希望解题数多的选手排名更高。为此，你希望对于任意的 $k$（$1 \leq k \leq N-1$），任意 $k$ 道题目的分数之和都严格小于任意 $k+1$ 道题目的分数之和。

请问有多少种分配分数的方法？请将这个数对给定素数 $M$ 取模后输出。

输入格式

输入为一行，包含两个整数：

$N$ $M$

输出格式

输出分配分数的方法数对 $M$ 取模后的结果。

样例 1

输入

2 998244353

输出

3

样例 2

输入

3 998244353

输出

7

样例 3

输入

6 966666661

输出

66

样例 4

输入

96 925309799

输出

83779

说明/提示

限制条件

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

样例解释 1

可能的分配方法有 $(1, 1)$、$(1, 2)$、$(2, 2)$。

样例解释 2

可能的分配方法有 $(1, 1, 1)$、$(1, 2, 2)$、$(1, 3, 3)$、$(2, 2, 2)$、$(2, 2, 3)$、$(2, 3, 3)$、$(3, 3, 3)$。

由 ChatGPT 4.1 翻译