Mana Deal

問題文

AliceとBobは、期末試験で合体魔法を放つことになりました。
合体魔法は $r+0.5$ のMPを消費することで放てるのですが、AliceのMPは $r$ 、BobのMPは $1$ しかありません。
残りMPが少ないほど頭痛がするので、お互いMPはなるべく温存したいです。
そこで、二人は次のゲームを行うことにしました。
このゲームでは、どちらかが $r+0.5$ MPを手に入れるまで、以下のターンを繰り返します。

• 二人でじゃんけんを行う。負けた側は勝った側にMPの半分を譲渡する。

ゲーム終了時、 $r+0.5$ MPを持っている側が合体魔法を放ちます。
合体魔法を放った後AliceのMPがBobのMPより多い確率を $p_r$ とするとき、 $\sum_{r=1}^N p_r$ は有理数 $\frac{a}{b}$ として表されるので、 $ab^{-1} \bmod P$ を出力してください。

制約

• $1 \leq N \leq 10^6$
• $10^8 \leq P \leq 10^9$
• $P$ は素数
• 各確率 $p_r$ を既約分数 $\frac{a}{b}$ で表した時、 $b$ は $P$ と互いに素
• 入力される値はすべて整数

入力

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

出力

$\sum_{r=1}^N p_r \bmod P$ を一行に出力せよ。

サンプル 1

入力

3 998244353

出力

546657623

$p_1=\frac{1}{2},\ p_2=\frac{1}{3},\ p_3=\frac{2}{7}$ です。