Fence Painting Ways

You are given a fence with n posts and k different colors. Your task is to calculate the number of ways to paint the fence so that no more than two adjacent posts have the same color. In other words, you should not have three or more consecutive posts painted with the same color.

The answer can be very large, so output the result modulo \(10^9+7\).

inputFormat

The input consists of two space-separated integers, n (the number of posts) and k (the number of colors).

outputFormat

Output a single integer, which is the number of valid ways to paint the fence under the given constraints, modulo \(10^9+7\).

1 1

1