该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

求 $\displaystyle\ \sum_{i\ =\ 0}^{X-1}\ A^i$。

由于结果很大，输出对 $M$ 取模后的结果即可。

Format

Input

一行三个正整数，分别为 $A（\le10^9）$ 、 $X（\le10^{12}）$ 和 $M（\le10^9）$。

Output

一行中输出答案。

Samples

3 4 5

0

Limitation

1s, 1024KiB for each test case.