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 posts have the same colors. Since the answer can be large return it modulo 10^9 + 7.
Example 1:
Input:
N=3,  K=2 
Output: 6
Explanation: 
We have following possible combinations:
 
Example 2:
Input:
N=2,  K=4
Output: 16
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countWays() that takes n and k as parameters and returns the number of ways in which the fence can be painted.(modulo 10^{9} + 7)
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 5000
1 ≤ K ≤ 100

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



class Solution:

    def countWays(self,n,k):

        #code here.



Solutions:
class Solution:

	def countWays(self, n, k):
		dp = []
		for i in range(n):
			dp.append([0, 0])
		dp[0] = [k, 0]
		for i in range(1, n):
			dp[i][0] = (dp[i - 1][0] * (k - 1) + dp[i - 1][1] * (k - 1)) % (10 ** 9 + 7)
			dp[i][1] = dp[i - 1][0]
		return sum(dp[n - 1]) % (10 ** 9 + 7)


class Solution:

	def countWays(self, n, k):
		mod = 10 ** 9 + 7
		if n == 1:
			return k
		same = k
		diff = k * (k - 1)
		total = same + diff
		for i in range(3, n + 1):
			same = diff % mod
			diff = total * (k - 1) % mod
			total = (same + diff) % mod
		return total


class Solution:

	def countWays(self, n, k):
		mod = 1000000007
		if n == 0:
			return 0
		if n == 1:
			return k
		if n == 2:
			return k * k
		dp = [0] * (n + 1)
		dp[1] = k
		dp[2] = k * k
		for i in range(3, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) * (k - 1) % mod
		return dp[n]


class Solution:

	def countWays(self, n, k):
		mod = 1000000007
		if n == 0:
			return 0
		if n == 1:
			return k
		same = k % mod
		diff = k * (k - 1) % mod
		for i in range(3, n + 1):
			prev = diff % mod
			diff = (same + diff) * (k - 1) % mod
			same = prev % mod
		return (same + diff) % mod


import sys
sys.setrecursionlimit(10000)
import sys
sys.setrecursionlimit(10000)

class Solution:

	def getAns(self, n, col, len, dp, colors):
		m = 10 ** 9 + 7
		if n == 0:
			return 1
		if dp[n][col][len] != -1:
			return dp[n][col][len]
		notTake = 0
		for i in range(0, colors):
			if i != col:
				notTake += self.getAns(n - 1, i, 1, dp, colors)
		take = 0
		if len < 2:
			take = self.getAns(n - 1, col, len + 1, dp, colors)
		dp[n][col][len] = (notTake + take) % m
		return dp[n][col][len]

	def countWays(self, n, k):
		m = 10 ** 9 + 7
		dp = [0 for i in range(n + 1)]
		dp[1] = k
		same = k
		for i in range(2, n + 1):
			dp[i] = (same + dp[i - 1] * (k - 1)) % m
			same = dp[i - 1] * (k - 1) % m
		return dp[n]
		dp = [[[-1 for i in range(3)] for j in range(k)] for jj in range(n + 1)]
		val = self.getAns(n, k - 1, 0, dp, k)
		return val


class Solution:

	def countWays(self, n, k):
		if n == 1:
			return k
		if n == 2:
			return k + k * (k - 1)
		mod = 10 ** 9 + 7
		ans = self.solve(n, k)
		return ans % mod

	def solve(self, n, k):
		mod = 10 ** 9 + 7
		prev2 = k
		prev1 = k + k * (k - 1)
		for i in range(3, n + 1):
			ans = (prev2 * (k - 1) + prev1 * (k - 1)) % mod
			prev2 = prev1
			prev1 = ans
		return prev1


class Solution:

	def countWays(self, n, k):
		if n == 1:
			return k
		if n == 2:
			return k + k * (k - 1)
		mod = 10 ** 9 + 7
		ans = self.solve(n, k)
		return ans % mod

	def solve(self, n, k):
		mod = 10 ** 9 + 7
		dp = [0] * (n + 1)
		dp[1] = k
		dp[2] = k + k * (k - 1)
		for i in range(3, n + 1):
			dp[i] = (dp[i - 2] * (k - 1) + dp[i - 1] * (k - 1)) % mod
		return dp[n]


class Solution:

	def countWays(self, n, k):
		f = []
		f.append(0)
		if n == 0:
			return f[0]
		f.append(k)
		if n == 1:
			return f[1]
		f.append(k * k)
		if n == 2:
			return f[2]
		for i in range(3, n + 1):
			f.append(f[i - 1] * (k - 1) + f[i - 2] * (k - 1))
		return f[n] % 1000000007


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def solve(self, n, k, dp, mod):
		if n <= 0:
			return 0
		if n == 1:
			return k % mod
		if n == 2:
			return k ** 2 % mod
		if dp[n][k] != -1:
			return dp[n][k]
		summ = (self.solve(n - 1, k, dp, mod) + self.solve(n - 2, k, dp, mod)) % mod
		dp[n][k] = (k - 1) * summ % mod
		return dp[n][k]

	def countWays(self, n, k):
		mod = 10 ** 9 + 7
		if n == 1:
			return k % mod
		if n == 2:
			return k ** 2 % mod
		dp = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]
		ans = self.solve(n, k, dp, mod)
		return ans


import sys
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def solve(n, k, dp):
	if n == 1:
		return k
	if n == 2:
		return add(k, mul(k, k - 1))
	if dp[n][k] != -1:
		return dp[n][k]
	inc1 = mul(solve(n - 2, k, dp), k - 1)
	inc2 = mul(solve(n - 1, k, dp), k - 1)
	summ = add(inc1, inc2)
	dp[n][k] = summ
	return dp[n][k]

class Solution:

	def countWays(self, n, k):
		if n == 1:
			return k
		if n == 2:
			return k ** 2 % mod
		dp = [[-1 for _ in range(k + 1)] for _ in range(n + 1)]
		return solve(n, k, dp)


class Solution:

	def rec_sol(self, n, N, k):
		if k == 0:
			return 0
		if n == N:
			if n == 1:
				return k
			if n == 2:
				return k + k * (k - 1)
			return self.rec_sol(n - 1, N, k) * k + self.rec_sol(n - 2, N, k) * k
		else:
			if n == 1:
				return k - 1
			if n == 2:
				return k - 1 + (k - 1) * (k - 1)
			return self.rec_sol(n - 1, N, k) * k + self.rec_sol(n - 2, N, k) * k
		return self.rec_sol(n - 1, N, k) * (k - 1) + self.rec_sol(n - 2, N, k) * (k - 1)

	def dp_sol(self, n, k):
		if k == 0:
			return 0
		if n == 1:
			return k
		if n == 2:
			return k + k * (k - 1)
		else:
			suma1 = k - 1
			suma2 = k * k - k
			for i in range(3, n + 1):
				if i == n:
					temp = suma2 * k + suma1 * k
				else:
					temp = suma2 * (k - 1) + suma1 * (k - 1)
					suma1 = suma2
					suma2 = temp
			return temp % 1000000007

	def countWays(self, n, k):
		return self.dp_sol(n, k)


class Solution:

	def countWays(self, n, k):
		MOD = 10 ** 9 + 7
		dp = [[0 for _ in range(2)] for _ in range(n + 1)]
		dp[1][0] = k
		dp[1][1] = 0
		for i in range(2, n + 1):
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)
			dp[i][1] = dp[i - 1][0]
			dp[i][0] %= MOD
			dp[i][1] %= MOD
		return (dp[n][0] + dp[n][1]) % MOD


import sys
sys.setrecursionlimit(10000000)

class Solution:

	def solve(self, n, k, dp):
		if n == 1:
			return k
		if n == 2:
			return k + k * (k - 1)
		if dp[n] != -1:
			return dp[n]
		a = self.solve(n - 2, k, dp)
		ans_a = a * (k - 1)
		b = self.solve(n - 1, k, dp)
		ans_b = b * (k - 1)
		ans = ans_a + ans_b
		dp[n] = ans
		return dp[n]

	def countWays(self, n, k):
		dp = [-1 for i in range(n + 1)]
		ans = self.solve(n, k, dp)
		return ans % 1000000007


class Solution:

	def countWays(self, n, k):
		if n == 1:
			return k
		if n == 2:
			return k ** 2
		(same, different) = (k, k ** 2 - k)
		for _ in range(2, n):
			newSame = different
			newDifferent = (same + different) * (k - 1)
			(same, different) = (newSame, newDifferent)
		return (same + different) % (10 ** 9 + 7)


class Solution:

	def countWays(self, n, k):
		if n == 1:
			return k
		limit = 1000000007
		(a, b) = (1, k)
		for i in range(3, n + 1):
			(a, b) = (b, (k - 1) * (a + b) % limit)
		return k * b % limit


import sys

class Solution:

	def countWays(self, n, k):
		if n <= 0:
			return 0
		if n == 1:
			return k
		dp = [-1] * (1 + n)
		dp[0] = 0
		dp[1] = k
		dp[2] = k * (k - 1) + k
		for i in range(3, n + 1):
			ans = 0
			ans2 = 0
			if i - 1 >= 0:
				ans = dp[i - 1] % 1000000007
			if i - 2 >= 0:
				ans2 = dp[i - 2] % 1000000007
			ans = (ans + ans2) % 1000000007
			ans = ans * (k - 1) % 1000000007
			dp[i] = ans
		return dp[n]


import sys

class Solution:

	def countWays(self, n, k):
		sys.setrecursionlimit(6000)
		dp = [-1] * (1 + n)

		def findsol(n, k):
			if n == 1:
				return k
			if n == 2:
				return k * (k - 1) + k
			if n <= 0:
				return 0
			if dp[n] != -1:
				return dp[n]
			ans = findsol(n - 1, k) % 1000000007
			ans2 = findsol(n - 2, k) % 1000000007
			ans = (ans + ans2) % 1000000007
			ans = ans * (k - 1) % 1000000007
			dp[n] = ans
			return ans
		return findsol(n, k)


class Solution:

	def countWays(self, n, k):
		if n == 0:
			return 0
		if n == 1:
			return k
		if n == 2:
			return k * k
		res = [0] * (n + 1)
		res[1] = k
		res[2] = k * k
		for i in range(3, n + 1):
			res[i] = (k - 1) * (res[i - 1] + res[i - 2]) % (10 ** 9 + 7)
		return res[n]