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

$1.$The first argument is an integer A

$2.$The second argument is an integer B$.$

$3.$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$

$[$C$++]$ Syntax Tips

$//$ Prints help message the console

$//$ Returns a string

string helloworld$($string name$)($

cout $<<$ "This prints to the console when you Run Tests" $<<$ endl; return "Hello,$+$ name:

$\}$