# Divide and Add

Given three integers $a$, $n$ and $m$. Calculate the value $\frac{1}{a} + \frac{2}{a^2} + \frac{3}{a^3} \cdots + \frac{n}{a^n} \pmod{m}$.

## Input format
The input contains three integers $a$, $n$ and $m$ ($1 \le a \le 10^9$, $2 \le n \le 10^6$, $2 \le m \le 10^9 + 9$ ).

## Output format
Print one integer - the value of $1/a + 2/a^2 + 3/a^3 \cdots + n/a^n \pmod{m}$. If at least one of divisions cannot be done, print $-1$ instead.

### Sample 1

#### Input

1 5 100

#### Output

15

### Sample 2

#### Input

2 1000 1000000008

#### Output

-1