Alex loves coloring balls. Today he decided to color N balls that are placed in a line from left to right.Alex has M different types of colors and can color each ball with one of the M colors.He wants to color each ball such that color of first K balls from left side are distinct and color of first K balls from right side are distinct. Being a maths lover before coloring balls Alex wants to calculate the number of ways to color balls as described above. Help Alex to calculate number of ways modulo \(10^{9}\)+7. Two ways are considered different if atleast one ball has different colors in both ways.
Input
The input contains three space separated integers N,M and K.
Output
Print number of ways modulo \(10^{9}\)+7.
Constraints
1 ≤K ≤ M ≤N≤ \(10^{5}\).
6 3 3
36
There are total 6 balls and 3 colors and first 3 balls should have distinct colors and last 3 balls must have distinct colors, so no. of ways of coloring first 3 balls with distinct colors is 6 and number of ways of coloring last 3 balls with distinct colors is also 6 hence total number of ways is 6*6 = 36.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
No editorial available for this problem.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor