AT_agc077_d [AGC077D] Range Replace 2

给定一个正整数 $N$ 和一个素数 $P$。 存在一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$，初始所有元素均为 $0$。 你可以进行如下操作若干次（可以为零次）： - 选择一对整数 $(l, r)$，满足 $1\leq l\leq r\leq N$。将 $A_l,A_{l+1},\ldots,A_r$ 的每一项都替换为 $\dfrac{r(r-1)}{2}+l$。 请你求出，经过若干次操作后，所有可能得到的序列 $A$ 的方案数，答案对 $P$ 取模。

输入由标准输入给出，格式如下： ``` N\ P ```

输出一个整数，表示答案。

### 样例解释 1 两种可能的序列 $A$ 分别为 $(0)$ 和 $(1)$。 ### 样例解释 2 共有七种可能的序列 $A$，分别为 $(0,0)$、$(0,3)$、$(1,0)$、$(1,2)$、$(1,3)$、$(2,2)$、$(2,3)$。 ### 数据范围 - $1\leq N\leq 5000$ - $P$ 是满足 $10^8