Laith thinks he's good at counting, he's not. Ahmad gave him a problem to prove him wrong, the problem is as follows:
You have a dart board represented by $n$ concentric circles and you have $c$ colors. You have to color the space between every two consecutive circles, as well as the circle in the middle.
A coloring is considered valid if there are no two consecutive spaces with the same color.
For example, if $n = 3$ and $c = 3$, and the colors are red, blue, green. Then the following colorings are:
Your task is to count the number of valid colorings for given $n$ and $c$. Since the answer can be very large print it modulo $1000000007$.
Laith didn't know how to solve this problem; but he also didn't want to get embarrassed in front of his master Zagha. Laith asks you if you can help him solve this problem.
Input
The first and only line has two integers $n,c\ (1\leq n,c\leq 10^9)$ --- the number of circles and the number of colors.
Output
Print the total number of valid colorings modulo $1000000007$.
Samples
| Input | Output |
|---|---|
3 3 Copy
|
12 Copy
|
8 1 Copy
|
0 Copy
|
1000000000 7 Copy
|
178780151 Copy
|