You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
- Every post must be painted exactly one color.
- At most one pair of adjacent fence posts can have the same color.
Given the two integers n and k, return the number of ways you can paint the fence.
Example 1:
Input: n = 3, k = 2 Output: 6 Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there can only be at most one pair of adjacent posts that are the same color.
Example 2:
Input: n = 1, k = 1 Output: 1
Example 3:
Input: n = 7, k = 2 Output: 42
Constraints:
1 <= n <= 501 <= k <= 105- The answer is guaranteed to be in the range
[0, 231 - 1]for the givennandk.