Summation of Power Weighted Terms

Given three integers n, a, and k, compute the sum

$$ S = \sum_{i=1}^n i^k a^i $$

and output the answer modulo $$10^9+7$$.

inputFormat

The input consists of a single line containing three space-separated integers: n, a, and k.

outputFormat

Output a single integer, the value of the summation modulo $$10^9+7$$.

sample

3 2 1

34