問題文

$3$ 以上の正整数 $N$ と素数 $P$ が与えられます．また，あなたは $a = N$ で初期化された変数 $a$ を持っています．
あなたは $a$ が $2$ 以下になるまで，以下の操作を繰り返し行います．

• $1$ 以上 $a$ 以下の非負整数 $b$ を一様ランダムに選択する．$a$ を $b$ で割ったあまりを $c$ として，$a$ を $a - c$ で置き換える．ここで，$b$ は操作ごとに独立して選択されます．

操作回数の期待値を $\mathrm{mod} \ P$ で求めてください．

ここで，入力で与えられる $N, P$ について $\mathrm{mod} \ P$ で答えが定義できる入力のみ与えられます．
厳密には，入力で与えられる $N$ について操作回数の期待値は必ず有理数であり互いに素な非負整数 $x, y$ を用いて $\frac{x}{y}$ と表すことが保証されます．また入力で与えられる $P$ について $y \not\equiv 0 \ (\mathrm{mod} \ P)$ であることが保証されます．このとき $yz \equiv x \ (\mathrm{mod} \ P), 0 \leq z < P$ なる非負整数 $z$ が一意に定まるため，この $z$ を出力してください．

入力

$N\ \ P$

• $3 \leq N \leq 3 \times 10^5$
• $9 \times 10^8 \leq P \leq 10^9$
• $P$ は素数
• 入力はすべて整数
• $\mathrm{mod} \ P$ で答えが定義できる

出力

操作回数の期待値を $\mathrm{mod} \ P$ で出力し，改行してください．

サンプル

5 998244353

332748125

50 998244353

411546056

500 998244353

854038998