問題一覧 > 通常問題

No.613 Solitude by the window

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

問題文

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

入力

N M

$N$は整数で、$1\le N \le 10^{18}$。
$M$は素数で、$2\le M \le 1100000000=1.1\times 10^9$。

出力

最後に改行してね。

サンプル

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

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

$n$秒後の石の個数を$a_n$とすると、任意の0以上の整数$n$に対して、$a_n \equiv 2 \pmod 5$が成り立つわ。

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

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