問題文

MMNMMさんは屋台で賭け事をしています．
この賭け事は小さい勝負を繰り返すもので，勝ち続ける限りいくらでも続き，負けた時点で終了になります．
この賭け事には正の整数 a ， M が定まっています．
1回目の勝負に勝つと 1 点がもらえ， n 回目の勝負( n>1 )回目の勝負に勝つと， n-1 回目の勝負でもらった点数 x 点について， a^x 点がもらえます．
勝負に負けると 0 点がもらえます．
賭け事が終了したときの合計点数を M で割ったあまりが最終的なポイントとなり，ポイントに応じて景品がもらえます．
MMNMMさんは賭け事で合計 K 回の勝負をしました(つまり， K-1 回勝ちました)．MMNMMさんの最終的なポイントを求めてください．

制約

すべてのテストケースは以下の制約を満たします．

• 1 \leq a \leq 10^{18}
• 1 \leq M \leq 10^9+7 ， M は素数
• 1 \leq K \leq 10^{18}

入力例 1

2 19 6

出力例 1

9

1 + 2 + 2^2 + 2^{2^2} + 2^{2^{2^2}} + 0 = 1 + 2 + 4 + 16 + 65536 + 0 = 65559 で， 65559 を 19 で割ったあまりは 9 なので，MMNMMさんは9ポイントを得ることができます．

入力例 2

3 101 3

出力例 2

4

入力例 3

1333 1000000007 8691201001

出力例 3

589246632