AT_agc071_e [AGC071E] Procrastinate Counter

For a permutation $ P=(P_1,P_2,\dots,P_N) $ of $ (1,2,\dots,N) $ , define a length- $ N $ integer sequence $ f(P) $ as follows. - Initialize an integer sequence $ X $ with $ X=(P_1,P_2,\dots,P_N) $ . Repeat the following operation until $ X $ is a strictly increasing sequence. (It can be shown that $ X $ will be a strictly increasing sequence in a finite number of operations for any permutation $ P $ .) - Let $ k $ be the smallest index $ i $ ( $ 1 \leq i < N $ ) such that $ X_i > X_{i+1} $ . Move the $ k $ -th element of $ X $ to the end. More precisely, replace $ X $ with $ (X_1,X_2,\dots,X_{k-1},X_{k+1},X_{k+2},\dots,X_N,X_{k}) $ . Let $ C_x $ be the number of times an integer $ x $ is moved to the end during this series of operations. Then, define $ f(P)=(C_1,C_2,\dots,C_N) $ . Find the number, modulo a prime number $ M $ , of distinct sequences that can occur as $ f(P) $ .

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

Print the answer.

### Sample Explanation 1 For example, when $ P=(1,4,3,2) $ , we initialize $ X=(1,4,3,2) $ and perform operations as follows: 1. Since $ X_1 \leq X_2 $ but $ X_2 > X_3 $ , the element $ X_2=4 $ is moved to the end, and $ X $ becomes $ (1,3,2,4) $ . 2. $ X_2=3 $ is moved to the end, and $ X $ becomes $ (1,2,4,3) $ . 3. $ X_3=4 $ is moved to the end, and $ X $ becomes $ (1,2,3,4) $ . The number of times $ 1,2,3,4 $ are moved to the end is $ 0,0,1,2 $ , respectively, so $ f(P)=(0,0,1,2) $ . ### Constraints - $ 1 \leq N \leq 500 $ - $ 10^8 \leq M \leq 10^9 $ - $ M $ is prime. - All input values are integers.