AT_agc071_e [AGC071E] Procrastinate Counter

$ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ に対し、長さ $ N $ の整数列 $ f(P) $ を以下のように定めます。 - 整数列 $ X $ を $ X=(P_1,P_2,\dots,P_N) $ で初期化し、 $ X $ が単調増加数列になるまで以下の操作を行い続ける。なお、任意の順列 $ P $ に対し、 $ X $ は有限回の操作によって単調増加数列になることが示せる。 - $ X_i > X_{i+1} $ を満たす最小の $ i\ (1 \leq i < N) $ を $ k $ とする。 $ X $ の $ k $ 項目を末尾に移動する。より正確には、 $ X $ を $ (X_1,X_2,\dots,X_{k-1},X_{k+1},X_{k+2},\dots,X_N,X_{k}) $ で置き換える。 一連の操作で整数 $ x $ が末尾に移動させられた回数を $ C_x $ とし、 $ f(P)=(C_1,C_2,\dots,C_N) $ と定める。 $ f(P) $ としてありうるものの種類数を素数 $ M $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

答えを出力せよ。

### Sample Explanation 1 例えば $ P=(1,4,3,2) $ の場合、 $ X $ は $ X=(1,4,3,2) $ で初期化され、操作は以下のように行われます。 1. $ X_1 \leq X_2 $ かつ $ X_2 > X_3 $ であるため、 $ X_2=4 $ が末尾に移動し、 $ X $ は $ (1,3,2,4) $ に変化する 2. $ X_2=3 $ が末尾に移動し、 $ X $ は $ (1,2,4,3) $ に変化する 3. $ X_3=4 $ が末尾に移動し、 $ X $ は $ (1,2,3,4) $ に変化する $ 1,2,3,4 $ が末尾に移動させられた回数はそれぞれ $ 0,0,1,2 $ 回であるため、 $ f(P)=(0,0,1,2) $ となります。 ### Constraints - $ 1 \leq N \leq 500 $ - $ 10^8 \leq M \leq 10^9 $ - $ M $ は素数 - 入力される値はすべて整数