AT_abc293_e [ABC293E] Geometric Progression

[problemUrl]: https://atcoder.jp/contests/abc293/tasks/abc293_e 整数 $ A,\ X,\ M $ が与えられます。$ \displaystyle\ \sum_{i\ =\ 0}^{X-1}\ A^i $ を $ M $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ A $ $ X $ $ M $

答えを出力せよ。

### 制約 - $ 1\ \leq\ A,\ M\ \leq\ 10^9 $ - $ 1\ \leq\ X\ \leq\ 10^{12} $ - 入力はすべて整数 ### Sample Explanation 1 $ 3^0\ +\ 3^1\ +\ 3^2\ +\ 3^3\ =\ 40 $ です。$ 40 $ を $ 7 $ で割った余りは $ 5 $ であるため、$ 5 $ を出力します。