Find the number of unique words consisting of lowercase alphabets only of length N that can be formed with at-most K contiguous vowels. 
Example 1:
Input:
N = 2
K = 0
Output:
441
Explanation:
Total of 441 unique words are possible
of length 2 that will have K( =0) vowels
together, e.g. "bc", "cd", "df", etc are
valid words while "ab" (with 1 vowel) is
not a valid word.
Example 2:
Input:
N = 1
K = 1
Output:
26
Explanation:
All the english alphabets including
vowels and consonants; as atmost K( =1)
vowel can be taken.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function kvowelwords() which takes an Integer N, an intege K and returns the total number of words of size N with atmost K vowels. As the answer maybe to large please return answer modulo 1000000007.
Expected Time Complexity: O(N*K)
Expected Auxiliary Space: O(N*K)
Constraints:
1 ≤ N ≤ 1000
0 ≤ K ≤ N

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def kvowelwords(self, N,K):

		# code here







Solutions:
NV = 5
NC = 26 - NV

class Solution:

	def kvowelwords(self, n, k):
		memo = [[0 for _ in range(k + 1)] for _ in range(n)]
		memo += [[1] + [0 for _ in range(1, k + 1)]]
		for i in range(n - 1, -1, -1):
			memo[i][0] = NC * sum(memo[i + 1]) % 1000000007
			memo[i][1:] = map(lambda x: NV * x % 1000000007, memo[i + 1][0:-1])
		return sum(memo[0]) % 1000000007


class Solution:

	def kvowelwords(self, N, K):
		(n, k, mod) = (N, K, 1000000007)
		if k == 0:
			return pow(21, N, mod)
		dp = [[0] * (k + 1) for i in range(0, n + 1)]
		dp[1][0] = 21
		dp[1][1] = 5
		for i in range(2, n + 1):
			for j in range(0, k + 1):
				if j > i:
					break
				if j == 0:
					dp[i][j] = sum(dp[i - 1]) * 21 % mod
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5 % mod
		return sum(dp[-1]) % mod


class Solution:

	def kvowelwords(self, N: int, K: int) -> int:
		mod = 10 ** 9 + 7
		dp = [1]
		dpp = [1]
		for _ in range(K):
			dpp.append(dpp[-1] * 5 % mod)
		for i in range(1, N + 1):
			tot = 0
			for j in range(min(i + 1, K + 1)):
				count = dpp[j]
				if i > j:
					count = count * 21 * dp[i - j - 1] % mod
				tot = (tot + count) % mod
			dp.append(tot)
		return dp[-1]


class Solution:

	def power(self, x, y, p):
		res = 1
		x = x % p
		if x == 0:
			return 0
		while y > 0:
			if y % 2 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res

	def kvowelwords(self, N, K):
		MOD = 1000000007
		dp = [[0 for j in range(K + 1)] for i in range(N + 1)]
		sum = 1
		for i in range(1, N + 1):
			dp[i][0] = sum * 21
			dp[i][0] %= MOD
			sum = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
				elif j == i:
					dp[i][j] = self.power(5, i, MOD)
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				dp[i][j] %= MOD
				sum += dp[i][j]
				sum %= MOD
		return sum


class Solution:

	def kvowelwords(self, N, K):
		MOD = 1000000007
		dp = [[0 for i in range(K + 1)] for j in range(N + 1)]
		dp[0][0] = 1
		sum = 1
		for i in range(1, N + 1):
			dp[i][0] = sum * 21
			dp[i][0] %= MOD
			sum = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				dp[i][j] %= MOD
				sum += dp[i][j]
				sum %= MOD
		return sum


class Solution:

	def kvowelwords(self, N, K):
		dp = [[0 for j in range(0, K + 1)] for i in range(0, N + 1)]
		sum = 1
		for i in range(1, N + 1):
			dp[i][0] = 21 * sum
			sum = dp[i][0]
			for j in range(1, K + 1):
				if i < j:
					continue
				if i == j:
					dp[i][j] = 5 ** i
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				sum += dp[i][j]
		return sum % (10 ** 9 + 7)


class Solution:

	def kvowelwords(self, N, K):
		dp = [[0] * (K + 1) for _ in range(N + 1)]
		total = 1
		mod = 10 ** 9 + 7
		for i in range(1, N + 1):
			dp[i][0] = total * 21
			total = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
				elif j == i:
					dp[i][j] = 5 ** i
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				total += dp[i][j]
		total = total % mod
		return total


class Solution:

	def kvowelwords(self, N, K):

		def power(x, y, p):
			res = 1
			x = x % p
			if x == 0:
				return 0
			while y > 0:
				if y & 1:
					res = res * x % p
				y = y >> 1
				x = x * x % p
			return res
		if K == 0:
			return 21 ** N
		dp = [[0] * (K + 1) for ele in range(N + 1)]
		dp[1][0] = 21
		dp[1][1] = 5
		m = 10 ** 9 + 7
		for i in range(2, N + 1):
			for k in range(K + 1):
				if k == 0:
					dp[i][k] = sum([dp[i - 1][j] % m for j in range(K + 1)]) % m * 21 % m
				elif k > i:
					dp[i][k] = 0
				elif k == i:
					dp[i][k] = power(5, i, m)
				else:
					dp[i][k] = dp[i - 1][k - 1] % m * 5 % m
		return sum([dp[N][i] % m for i in range(K + 1)]) % m


class Solution:

	def kvowelwords(self, N, K):
		dp = [[0 for _ in range(K + 1)] for __ in range(N + 1)]
		BOUND = 1000000007
		rowSum = 1
		for i in range(1, N + 1):
			rowSum = rowSum * 21 % BOUND
			dp[i][0] = rowSum
			for j in range(1, K + 1):
				if j > i:
					break
				elif j == i:
					dp[i][j] = 5 ** j % BOUND
				else:
					dp[i][j] = 5 * dp[i - 1][j - 1] % BOUND
				rowSum = (rowSum + dp[i][j]) % BOUND
		return sum(dp[N]) % BOUND


class Solution:

	def kvowelwords(self, n, k):
		MOD = 1000000007
		dp = [[0] * (k + 1) for _ in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			dp[i][0] = sum(dp[i - 1]) * 21
			for j in range(1, k + 1):
				dp[i][j] += dp[i - 1][j - 1] * 5
		return sum(dp[-1]) % MOD


import sys
sys.setrecursionlimit(1000000)
MOD = 1000000007

def f(S, idx, k, N, K, dp):
	if idx == N and k >= 0:
		return 1
	elif idx == N or k < 0:
		return 0
	else:
		if dp[idx][k] != -1:
			return dp[idx][k]
		ans = 0
		vowels = [0, 4, 8, ord('o') - ord('a'), ord('u') - ord('a')]
		for i in range(26):
			S += chr(ord('a') + i)
			if i in vowels:
				ans += f(S, idx + 1, k - 1, N, K, dp)
			else:
				ans += f(S, idx + 1, K, N, K, dp)
		ans %= MOD
		dp[idx][k] = ans
		return ans

def power(x, y):
	if x == 0:
		return 0
	res = 1
	while y:
		if y & 1:
			res = res * x
			res %= MOD
		x *= x
		x %= MOD
		y >>= 1
	return res

class Solution:

	def kvowelwords(self, N, K):
		dp = [[-1 for i in range(K + 1)] for i in range(N + 1)]
		sum = 1
		for i in range(1, N + 1):
			dp[i][0] = sum * 21
			dp[i][0] %= MOD
			sum = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
				elif j == i:
					dp[i][j] = power(5, i)
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				dp[i][j] %= MOD
				sum += dp[i][j]
				sum %= MOD
		return sum


class Solution:

	def kvowelwords(self, n, k):
		MOD = pow(10, 9) + 7
		if k == 0:
			return 21 ** n % MOD
		dp = [[0 for i in range(2)] for j in range(n + 5)]
		dp[0][0] = 1
		dp[0][1] = 0
		sm = 5
		for i in range(1, n + 1):
			dp[i][0] = (dp[i - 1][1] + dp[i - 1][0]) * 21 % MOD
			dp[i][1] = sm
			if i >= k:
				sm = (sm - dp[i - k][0] * pow(5, k) % MOD + MOD) % MOD
			sm = (sm + dp[i][0]) % MOD
			sm = sm * 5 % MOD
		return (dp[n][0] + dp[n][1]) % MOD


from typing import *

class Solution:

	def kvowelwords(self, N, K):
		mod = 1000000007
		dp = [1]
		dpp = [1]
		for _ in range(K):
			dpp.append(dpp[-1] * 5 % mod)
		for i in range(1, N + 1):
			tot = 0
			for j in range(min(i + 1, K + 1)):
				count = dpp[j]
				if i > j:
					count = count * 21 * dp[i - j - 1] % mod
				tot = (tot + count) % mod
			dp.append(tot)
		return dp[-1]


class Solution:

	def kvowelwords(self, N, K):
		arr = [1] * (K + 2)
		arr[0] = 21
		if K > 0:
			arr[1] = 5
		for i in range(2, len(arr) - 1):
			arr[i] = 0
		arr[-1] = sum(arr[:-1])
		for i in range(1, N):
			new = [0] * (K + 2)
			new[0] = arr[-1] * 21
			for j in range(1, len(arr) - 1):
				new[j] = arr[j - 1] * 5
			new[-1] = sum(new[:-1])
			arr = new[:]
		return arr[-1] % 1000000007


class Solution:

	def kvowelwords(self, n, k):
		mod = 1000000007
		dp = [[1] * (k + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(0, k + 1):
				if j == 0:
					dp[i][j] = 21 * dp[i - 1][k] % mod
				else:
					dp[i][j] = (21 * dp[i - 1][k] % mod + 5 * dp[i - 1][j - 1] % mod) % mod
		return dp[n][k]


from functools import lru_cache
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def kvowelwords(self, n, k):
		mo = 10 ** 9 + 7

		@lru_cache(None)
		def f(i, p):
			if i == n:
				return 1
			ans = 21 * f(i + 1, 1) % mo
			z = 0
			a = 5
			if p == 1:
				for j in range(1, k + 1):
					if i + j > n:
						break
					z = (z + a * f(i + j, 0)) % mo
					a *= 5
			return (z + ans) % mo
		return f(0, 1)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def kvowelwords(self, N, K):

		def power(x, y, p):
			res = 1
			x = x % p
			if x == 0:
				return 0
			while y > 0:
				if y & 1:
					res = res * x % p
				y = y >> 1
				x = x * x % p
			return res
		(i, j) = (0, 0)
		MOD = 1000000007
		dp = [[0 for i in range(K + 1)] for i in range(N + 1)]
		sum = 1
		for i in range(1, N + 1):
			dp[i][0] = sum * 21
			dp[i][0] %= MOD
			sum = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
				elif j == i:
					dp[i][j] = power(5, i, MOD)
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				dp[i][j] %= MOD
				sum += dp[i][j]
				sum %= MOD
		return sum
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, K) = map(int, input().split())
		ob = Solution()
		ans = ob.kvowelwords(N, K)
		print(ans)


NV = 5
NC = 26 - NV

class Solution:

	def kvowelwords(self, n, k):
		memo = [[0 for _ in range(k + 1)] for _ in range(n)]
		memo += [[1] + [0 for _ in range(1, k + 1)]]
		for i in range(n - 1, -1, -1):
			memo[i][0] = NC * sum(memo[i + 1]) % 1000000007
			memo[i][1:] = map(lambda x: NV * x % 1000000007, memo[i + 1][0:-1])
		return sum(memo[0]) % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, K) = map(int, input().split())
		ob = Solution()
		ans = ob.kvowelwords(N, K)
		print(ans)


class Solution:

	def kvowelwords(self, N, K):
		mod = 10 ** 9 + 7
		if K == 0:
			return (21 ** N + mod) % mod
		pow_5 = [0] * (N + 1)
		pow_5[0] = 1
		for i in range(1, N + 1):
			pow_5[i] = pow_5[i - 1] * 5 % mod
		dp = [0] * (N + 1)
		dp[0] = 1
		for i in range(1, N + 1):
			dp[i] = (dp[i] + 21 * dp[i - 1] % mod + mod) % mod
			for j in range(i, i - K, -1):
				if j > 1:
					dp[i] = (dp[i] + pow_5[i - j + 1] * 21 % mod * dp[j - 2] % mod % mod) % mod
				else:
					dp[i] = (dp[i] + (pow_5[i - j + 1] + mod) % mod) % mod
					break
		return dp[N]


class Solution:

	def __init__(self):
		self.d = {}

	def kvowelwords(self, N, K):
		temp = []
		for i in range(N + 1):
			r = []
			for j in range(K + 1):
				r.append(0)
			temp.append(r)
		summ = 1
		for i in range(1, N + 1):
			summ = summ * 21
			temp[i][0] = summ % 1000000007
			for j in range(1, K + 1):
				if i == j:
					temp[i][j] = 5 ** i % 1000000007
				elif j > i:
					temp[i][j] = 0
				else:
					temp[i][j] = temp[i - 1][j - 1] * 5 % 1000000007
				summ += temp[i][j]
		return summ % 1000000007


NV = 5
NC = 26 - NV

class Solution:

	def kvowelwords(self, N, K):
		temp = [[0 for _ in range(K + 1)] for _ in range(N)]
		temp += [[1] + [0 for _ in range(1, K + 1)]]
		for i in range(N - 1, -1, -1):
			temp[i][0] = NC * sum(temp[i + 1]) % 1000000007
			temp[i][1:] = map(lambda x: NV * x % 1000000007, temp[i + 1][0:-1])
		return sum(temp[0]) % 1000000007


class Solution:

	def kvowelwords(self, N, K):
		mod = 1000000007
		dp = [[1] * (K + 1) for _ in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(K + 1):
				if j == 0:
					dp[i][j] = 21 * dp[i - 1][K] % mod
				else:
					dp[i][j] = (5 * dp[i - 1][j - 1] % mod + 21 * dp[i - 1][K] % mod) % mod
		return dp[-1][-1]


class Solution:

	def kvowelwords(self, N, K):
		dp = [[1] * (K + 1) for i in range(N + 1)]
		p = 1000000007
		prev_sum = 1
		for i in range(1, N + 1):
			dp[i][0] = prev_sum * 21 % p
			prev_sum = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
					continue
				dp[i][j] = dp[i - 1][j - 1] * 5 % p
				prev_sum = (prev_sum + dp[i][j]) % p
		return prev_sum


class Solution:

	def kvowelwords(self, n, k):
		if k == 0:
			return 21 ** n
		else:
			M = [1] * (n + 1)
			for i in range(1, n + 1):
				if i <= k:
					M[i] = 26 ** i
				else:
					M[i] = sum([5 ** j * 21 * M[i - j - 1] for j in range(0, k + 1)])
			return M[n] % 1000000007


class Solution:

	def kvowelwords(self, N, K):
		dp = [[1 for i in range(K + 1)] for i in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(K + 1):
				if j == 0:
					dp[i][j] = dp[i - 1][K] * 21 % 1000000007
				else:
					diagnal = 5 * dp[i - 1][j - 1]
					prev = 21 * dp[i - 1][K]
					dp[i][j] = (diagnal + prev) % 1000000007
		return dp[N][K]


class Solution:

	def power(self, x, y, p):
		res = 1
		x = x % p
		if x == 0:
			return 0
		while y > 0:
			if y & 1 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res

	def kvowelwords(self, N, K):
		mod = 10 ** 9 + 7
		su = 1
		dp = [[0] * (K + 1) for i in range(N + 1)]
		for i in range(1, N + 1):
			dp[i][0] = su * 21
			dp[i][0] %= mod
			su = dp[i][0]
			for j in range(1, K + 1):
				if j > i:
					dp[i][j] = 0
				elif i == j:
					dp[i][j] = self.power(5, i, mod)
				else:
					dp[i][j] = dp[i - 1][j - 1] * 5
				dp[i][j] %= mod
				su += dp[i][j]
				su %= mod
		return su


from typing import *

class Solution:

	def kvowelwords(self, N, K):
		mod = 10 ** 9 + 7
		dp = [1]
		dpp = [1]
		for i in range(K):
			dpp.append(dpp[-1] * 5 % mod)
		for j in range(1, N + 1):
			tot = 0
			for l in range(min(j + 1, K + 1)):
				count = dpp[l]
				if j > l:
					count = count * 21 * dp[j - l - 1] % mod
				tot = (tot + count) % mod
			dp.append(tot)
		return dp[-1]


class Solution:

	def kvowelwords(self, N, K):
		large = 1000000007
		dp = [1]
		power5 = [1]
		for _ in range(K):
			power5.append(power5[-1] * 5 % large)
		for i in range(1, N + 1):
			total = 0
			for j in range(min(i + 1, K + 1)):
				count = power5[j]
				if i > j:
					count = count * 21 * dp[i - j - 1] % large
				total = (total + count) % large
			dp.append(total)
		return dp[-1]


class Solution:

	def kvowelwords(self, n, k):
		mod = 10 ** 9 + 7
		dp = [[1] * (k + 1) for _ in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(0, k + 1):
				if j == 0:
					dp[i][j] = 21 * dp[i - 1][k] % mod
				else:
					dp[i][j] = (5 * dp[i - 1][j - 1] % mod + 21 * dp[i - 1][k] % mod) % mod
		return dp[n][k]