题目描述

我们现在给出一个等比数列的首项 $a$ 和项数 $n$ ，并且给出它的公比 $q$ ，请输出 的值。

输入格式

共一行，分别给出 $a$ , $n$ , $q$ (使用空格隔开)

输出格式

输出 的值，并且对 $10^{9} + 7$ 取模。

样例

1 2 4

30

3 5 2

372

大样例

见附加文件 math*.in 与 math*.out 。

下载链接：math

样例解释

对于样例一：

这个等比数列首项为 $1$ ，项数为 $2$ ，公比为 $4$ ，所以这个数列是：

$A_i = [1 , 4]$

$（2 + 4） + （8 + 16） = 30$ 。

提示

可以寻找它们的通项公式进行解题。

数据规模与约定

对于前 $10\%$ 的数据， $n$ $\le$ $10^{3}$。

对于前 $20\%$ 的数据， $n$ $\le$ $10^{5}$。

对于 $100\%$ 的数据， $n$ $\le$ $10^{18}$ 。