Painting the Fence

Given a fence with n posts and k colors, find out the number of ways of painting the fence so that not more than two consecutive fences have the same colors. Since the answer can be large return it modulo 10^9 + 7.

Input Format:

First Parameter: number of posts in the fence n

Second Parameter: number of colors k

Output Format:

Return a single integer

Example 1:

Input: n=3,  k=2 
Output: 6
Explanation: 
We have following possible combinations:

Example 2:

Input: n=2,  k=4
Output: 16

Constraints

• 1 ≤ n ≤ 5000
• 1 ≤ k ≤ 100
• Expected Time Complexity: O(n)
• Expected Space Complexity: O(n)