#XMOJ12648. 独角仙

独角仙

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:rhinoceros.in 输出文件:rhinoceros.out

小明每年的 1 月 1 日一定会买 $B$ 只独角仙。

在每年 12 月 31 日清点数量时,独角仙的数量会变为当年 1 月 1 日数量的 $C$ 倍。

- 第 1 年 1 月 1 日购入 $B$ 只,年末数量为 $B \times C$。

- 第 2 年 1 月 1 日:原有 $B\times C$ 只,再买入 $B$ 只,合计 $B\times C+B$;年末变为 $(B\times C+B)\times C$。

求第 $D$ 年年末一共有多少只独角仙。

答案对 $10^9+7$ 取模。

输入格式

一行三个整数 $B,C,D$。

输出格式

输出第 $D$ 年年末独角仙数量模 $10^9+7$ 的结果。

样例

样例 1

1 2 3

14

样例说明:

第 11 年 11 月 11 日 11 只,年末 22 只。

第 $2$ 年 $1$ 月 $1$ 日加上新买的 $1$ 只共 $3$ 只,年末 $6$ 只。

第 $3$ 年 $1$ 月 $1$ 日加上新买的 $1$ 只共 $7$ 只,年末 $14$ 只。

样例 2

100 1 100

10000

样例说明:

C=1C=1,每年只新增 100100 只,一共 100×100=10000100\times 100=10000。

样例 3

123 456 789

198020583

样例 4

1000000000000 1000000000000 1000000000000

214111862

数据范围

对于 30% 的数据,$D \le 1000$。

对于 100% 的数据,$1 \le B,C,D \le 10^{12}$。