Problem Description

There is a sequence $ A $.

Let $A = \{b^0, b^1, b^2, \ldots, b^{a-1}\}$.

Perform the following operation $ c $ times:

• For every $ i $, set $A_i = A_0 + A_1 + \ldots + A_i$.

For example, when $ a = 4, b = 3, c = 2 $, the sequence evolves as follows:

1 3 9 27
After 1st operation: 1 4 13 40
After 2nd operation: 1 5 18 58

Output the value of $ A_{a-1} $ after the last operation, modulo $ 1,000,000,007 $. In the example above, the answer is $ 58 $.

Input Format

The input is given from the standard input in the following format:

$ a $ $ b $ $ c $

• The first line contains $ a, b, c $ separated by spaces.
• $ a $ is the length of the sequence.
• $ b $ is a constant related to the initial values of the sequence. The $ i $-th element is $ b^i $, with the leftmost element being the 0-th.
• $ c $ is the number of times the operation is performed.

Output Format

Output the following according to the standard output format:

• Print the value of the last element of the sequence after $ c $ operations, modulo $ 1,000,000,007 $, on a single line.

Sample Input and Output

Sample Input #1

4 3 2

Sample Output #1

58

Sample Input #2

6 1 5

Sample Output #2

252

Sample Input #3

123 456 789

Sample Output #3

271208111

Notes/Hints

Constraints

• $1 \leq a \leq 100,000$
• $1 \leq b, c \leq 1,000,000,000$

Subtasks

Subtask $ 1 $ \[ $ 12 $ points \]

• Satisfies $1 \leq a, b, c \leq 1,000$.

Subtask $ 2 $ \[ $ 48 $ points \]

• Satisfies $1 \leq a, b, c \leq 100,000$.

Subtask $ 3 $ \[ $ 40 $ points \]

• No additional constraints.

Sample Explanation 1

This is the same as the example in the problem statement.

Sample Explanation 2

The sequence evolves as follows:

1 1 1 1 1 1
After 1st operation: 1 2 3 4 5 6
After 2nd operation: 1 3 6 10 15 21
After 3rd operation: 1 4 10 20 35 56
After 4th operation: 1 5 15 35 70 126
After 5th operation: 1 6 21 56 126 252

Sample Explanation 3

Note to calculate the result modulo $ 1,000,000,007 $.

见题面 Input 部分

见题面 Output 部分