AT_agc077_d [AGC077D] Range Replace 2

You are given a positive integer $ N $ and a prime $ P $ . There is a sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ where all elements are $ 0 $ . You can repeat the following operation zero or more times. - Choose a pair of integers $ (l, r)\ (1\leq l\leq r\leq N) $ . Replace each of $ A_l,A_{l+1},\ldots,A_r $ with $ \dfrac{r(r-1)}{2}+l $ . Find the number, modulo $ P $ , of sequences that can be obtained as $ A $ after performing operations.

The input is given from Standard Input in the following format: > $ N $ $ P $

Output the answer.

### Sample Explanation 1 The two possible sequences $ A $ are $ (0) $ and $ (1) $ . ### Sample Explanation 2 The seven possible sequences $ A $ are $ (0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3) $ . ### Constraints - $ 1\leq N\leq 5000 $ - $ P $ is a prime satisfying $ 10^8\lt P\lt 10^9 $ . - All input values are integers.