正の整数 $N$ と素数 $P$ が与えられます。 $1, 2, \dots, N$ の順列 $(a_1, a_2, \dots, a_N)$ に対して、そのスコア $f(a)$ を以下のように定義します。

$$f(a) = \max\{i a_i \mid i = 1, 2, \dots, N\}$$

すべての順列に対するスコアの総和を $P$ で割った余りを求めてください。

入力

入力は以下の形式で与えられます。

$N$ $P$

ここで、$1 \le N \le 10^4$、$10^8 \le P < 10^9$ であり、$P$ は素数です。

出力

すべての順列に対するスコアの総和を $P$ で割った余りを出力してください。

入出力例

入力 1

10 100000007

出力 1

77379290

入力 2

1000 998244353

出力 2

168695631

注記

最初の例について、例えば $f(3, 9, 4, 10, 8, 2, 7, 5, 6, 1) = 54$ となります。 $10!$ 通りのすべての順列に対するスコアの総和は $277379304$ であり、これを素数 $P = 10^8 + 7$ で割った余りは $77379290$ となるため、$77379290$ を出力します。この入力において、素数 $P$ は $9$ 桁の整数 $10^8 + 7$ であることに注意してください。