题面翻译

现在的高考有些科目是赋分制的，你现在在命一套题，赋分规则如下：

• 有 $n$ 道还未赋分的题目，你需要给这 $n$ 道题目赋分。
• 设第 $i$ 道题目的分数为 $A_i$。给题目赋分的方案需要满足：
  • 对于任意 $i \in [2, n]$，$A_{i-1} \leq A_{i}$。
  • 对于任意 $i \in [1, n]$，$1 \leq A_{i} \leq n$。
  • 对于任意一个大小为 $k$（$1 \leq k < n$）的题目子集 $S$ 和任意一个大小为 $k+1$ 的题目子集 $T$，需要满足：$\sum_{x \in S}A_x < \sum_{x\in T}A_x$。
• 你需要计算，有多少种给题目赋分的方案，使得能满足上述三个条件。请求出答案对 $M$ 取模的结果。

输入格式

一行给出N，M

输出格式

如题

样例 #1

样例输入 #1

2 998244353

样例输出 #1

3

样例 #2

样例输入 #2

3 998244353

样例输出 #2

7

样例 #3

样例输入 #3

6 966666661

样例输出 #3

66

样例 #4

样例输入 #4

96 925309799

样例输出 #4

83779

提示

制約

• $2\ \leq\ N\ \leq\ 5000$
• $9\ \times\ 10^8\ <\ M\ <\ 10^9$