正整数 \(N\) と素数 \(P\) が与えられます。
\(1,2,\cdots,N\) の順列 \((a_1,a_2,\cdots,a_N)\) に対し、その スコア \(f(a)\) を以下の通りに定めます。
\[f(a) = \max\{ia_i\ |\ i=1,2,\cdots,N\}\]
全ての順列にわたるスコアの総和を \(P\) で割ったあまりを求めてください。
\(1\) 行に \(N,P\) がこの順に空白区切りで与えられる。 ( \(1\leq N\leq 10^4, 10^8\leq P\lt 10^9,P\) は素数)
すべての順列にわたるスコアの総和を \(P\) で割ったあまりを出力してください。
10 100000007
77379290
1000 998244353
168695631
\(1\) つ目のサンプルについて、例えば \(f(3,9,4,10,8,2,7,5,6,1)=54\) です。
\(10!\) 個全ての順列にわたるスコアの総和は \(277379304\) ですが、これを素数 \(P=10^8+7\) で割った余りの \(77379290\) を出力してください。 この入力における素数 \(P\) は \(9\) 桁の整数 \(10^8+7\) であることに注意してください。