Simple Recursion

By Kay Akashi

Problem Statement

Given a recursion rule $a_{n + 1} = pa_n + q$, where $a_1 = 1$, output the value of $a_X$ mod $(10^9 + 7)$ given $X$.

Constraints

$1 \leq p, q \leq 3000$.

Subtask 1 (25%)

$1 \leq X \leq 10^5$.

Subtask 2 (75%)

$1 \leq X \leq 10^{12}$.

Input

The first line of input contains $2$ integers, $p$ and $q$. The second line of input contains $1$ integer, $X$.

Output

Output a single integer, the value of $a_X$ mod $(10^9 + 7)$.

Examples

3 4
5

241

2915 2999
965736817718

56311101