题目描述

给定整数 $A$、$X$ 和 $M$，计算 $\\displaystyle \\sum_{i = 0}^{X-1} A^i$ 对 $M$ 取模的结果。

约束条件

• $1 \leq A, M \leq 10^9$
• $1 \leq X \leq 10^{12}$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$A$ $X$ $M$

输出

输出答案。

示例输入 1

3 4 7

示例输出 1

5

$3^0 + 3^1 + 3^2 + 3^3 = 40$，对 $7$ 取模等于 $5$，因此应该输出 $5$。

示例输入 2

8 10 9

示例输出 2

0

示例输入 3

1000000000 1000000000000 998244353

示例输出 3

919667211