Problem Description

An array is considered valid if there is no subarray longer than B where all elements are identical. Additionally, the array can only contain integers from the range $[1,$ C$].$ Determine the number of valid arrays of length A$.$ Since the result can be very large, return it modulo $(10^9+7).$

Problem Constraints

$(1<=$ A $<=10^9)$

$(1<=$ B $<=$ min$(50,$ A$))$

$(1<=$ C $<=10^5)$

Input Format

The first argument is an integer A$.$

The second argument is an integer B$.$

The third argument is an integer C$.$

Output Format

Return an integer representing the number of valid arrays.

Example Input

Input $1$:

A $=3$

B $=1$

C $=3$

Input $2$:

A $=3$

B $=3$

C $=2$

Example Output

Output $1$:

$12$

Output $2$:

$8$

Example Explanation

Explanation $1$:

The valid arrays are: $[1,2,1],[1,2,3],[1,3,1],[1,3,2],[2,1,3],[2,1,2],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,3].$

Explanation $2$:

All possible arrays of length $3$ are valid arrays.

$[$execution time limit$]2$ seconds $($cpp$)$

$[$memory limit$]1$ GB

$[$input$]$ integer$64$ a

$[$input$]$ integer b

$[$input$]$ integer c

$[$output$]$ integer$64$long long solution$($long long a$,$ int b$,$ int c$)\{\}$ complete the function