Coloring the Tiles

You are given a row of (n) tiles and (k) distinct colors. Your task is to determine the number of ways to color the row such that no two adjacent tiles have the same color. Formally, define (dp[1] = k) and for every (i \ge 2), (dp[i] = dp[i-1] \times (k-1)). Since the answer can be very large, compute it modulo (10^9+7).

inputFormat

The input consists of a single line containing two space-separated integers (n) and (k), where (n) is the number of tiles and (k) is the number of colors.

outputFormat

Output a single integer, the number of valid ways to color the row of tiles modulo (10^9+7).## sample

3 3

12