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 $ を満たす素数
• 入力される数値は全て整数