AT_agc077_d [AGC077D] Range Replace 2

正整数 $ N $ と素数 $ P $ が与えられます． すべての要素が $ 0 $ である長さ $ 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 $

答えを出力せよ．

### Sample Explanation 1 得られる $ A $ は $ (0),(1) $ の $ 2 $ 通りです． ### Sample Explanation 2 得られる $ A $ は $ (0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3) $ の $ 7 $ 通りです． ### Constraints - $ 1\leq N\leq 5000 $ - $ P $ は $ 10^8\lt P\lt 10^9 $ を満たす素数 - 入力される数値は全て整数