問題文

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}$

入力例 1Copy

2 19 6

出力例 1Copy

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ポイントを得ることができます．

入力例 2Copy

3 101 3

出力例 2Copy

4

入力例 3Copy

1333 1000000007 8691201001

出力例 3Copy

589246632