問題一覧 > 通常問題

No.613 Solitude by the window

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : 夕叢霧香(ゆうむらきりか) / テスター : uwi
3 ProblemId : 2019 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-13 12:49:33

問題文

最初石が2個ある。 この石は、1秒経つ度に、それぞれがその時点での石の個数+4個に同時に分裂する。 例えば、開始から1秒後には2×(2+4)=12個の石があり、 さらに1秒後には12×(12+4)=192個の石がある状態になる。 この時、N秒後の石の個数を、mod M (Mは素数)で求めてね。

入力

N M

Nは整数で、1≤N≤1018。
Mは素数で、2≤M≤1100000000=1.1×109。

出力

最後に改行してね。

サンプル

サンプル1
入力
2 10007
出力
192

サンプル2
入力
100000000 5
出力
2

n秒後の石の個数をanとすると、任意の0以上の整数nに対して、an≡2(mod5)が成り立つわ。

サンプル3
入力
1000000000000000000 1000000007
出力
688982865

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。