Given three integers x, y, and z, the task is to find the sum of all the numbers formed by 
having 4 at most x times, having 5 at most y times, and having 6 at most z times as a digit.
Note: Output the sum modulo 10^{9}+7.
Example 1:
Input: X = 1, Y = 1, Z = 1 
Output: 3675
Explanation: 4 + 5 + 6 + 45 + 54 + 56 
+ 65 + 46 + 64 + 456 + 465 
+ 546 + 564 + 645 + 654 = 3675
Example 2:
Input: X = 0, Y = 0, Z = 0
Output: 0
Explanation: No number can be formed
Your Task:  
You don't need to read input or print anything. Complete the function getSum() which takes X, Y and Z as input parameters and returns the integer value
Expected Time Complexity: O(X*Y*Z)
Expected Auxiliary Space: O(X*Y*Z)
Constraints:
0 ≤ X, Y, Z ≤ 60

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def getSum(self, X, Y, Z):

		# code here

Solutions:
import numpy as np

class Solution:

	def getSum(self, x, y, z):
		N = 101
		mod = int(1000000000.0) + 7
		exactsum = np.zeros((N, N, N))
		exactnum = np.zeros((N, N, N))
		ans = 0
		exactnum[0][0][0] = 1
		for i in range(x + 1):
			for j in range(y + 1):
				for k in range(z + 1):
					if i > 0:
						exactsum[i][j][k] += (exactsum[i - 1][j][k] * 10 + 4 * exactnum[i - 1][j][k]) % mod
						exactnum[i][j][k] += exactnum[i - 1][j][k] % mod
					if j > 0:
						exactsum[i][j][k] += (exactsum[i][j - 1][k] * 10 + 5 * exactnum[i][j - 1][k]) % mod
						exactnum[i][j][k] += exactnum[i][j - 1][k] % mod
					if k > 0:
						exactsum[i][j][k] += (exactsum[i][j][k - 1] * 10 + 6 * exactnum[i][j][k - 1]) % mod
						exactnum[i][j][k] += exactnum[i][j][k - 1] % mod
					ans += exactsum[i][j][k] % mod
					ans %= mod
		return int(ans)


from itertools import product

class Solution:

	def getSum(self, X, Y, Z):
		MOD = 10 ** 9 + 7
		ans = 0
		dp = {(0, 0, 0): (1, 0)}
		for (x, y, z) in product(range(X + 1), range(Y + 1), range(Z + 1)):
			if (x, y, z) in dp:
				continue
			mul = 10 ** (x + y + z - 1) % MOD
			(_subcnt, _subsums) = ([0] * 3, [0] * 3)
			if x > 0:
				(_subcnt[0], _subsums[0]) = dp[x - 1, y, z]
			if y > 0:
				(_subcnt[1], _subsums[1]) = dp[x, y - 1, z]
			if z > 0:
				(_subcnt[2], _subsums[2]) = dp[x, y, z - 1]
			cnt = sum(_subcnt)
			sums = (sum(_subsums) + mul * (_subcnt[0] * 4 + _subcnt[1] * 5 + _subcnt[2] * 6)) % MOD
			dp[x, y, z] = (cnt, sums)
			ans = (ans + sums) % MOD
		return ans


class Solution:

	def getSum(self, X, Y, Z):
		exact = []
		nums = []
		for i in range(X + 1):
			e2 = []
			n2 = []
			for j in range(Y + 1):
				e1 = []
				n1 = []
				for k in range(Z + 1):
					e1.append(0)
					n1.append(0)
				e2.append(e1)
				n2.append(n1)
			exact.append(e2)
			nums.append(n2)
		nums[0][0][0] = 1
		mod = 1000000007
		s = 0
		for i in range(X + 1):
			for j in range(Y + 1):
				for k in range(Z + 1):
					if i > 0:
						exact[i][j][k] += exact[i - 1][j][k] * 10 + 4 * nums[i - 1][j][k]
						nums[i][j][k] += nums[i - 1][j][k]
					if j > 0:
						exact[i][j][k] += exact[i][j - 1][k] * 10 + 5 * nums[i][j - 1][k]
						nums[i][j][k] += nums[i][j - 1][k]
					if k > 0:
						exact[i][j][k] += exact[i][j][k - 1] * 10 + 6 * nums[i][j][k - 1]
						nums[i][j][k] += nums[i][j][k - 1]
					exact[i][j][k] %= mod
					nums[i][j][k] %= mod
					s = (s + exact[i][j][k]) % mod
		return s


class Solution:

	def inverse(self, s, rem):
		return pow(s, rem - 2, rem)

	def getSum(self, X, Y, Z):
		rem = 10 ** 9 + 7
		(fact, ons) = ([1], [0])
		for i in range(1, X + Y + Z + 1):
			fact.append(fact[-1] * i % rem)
			ons.append((ons[-1] * 10 + 1) % rem)
		output = 0
		for i in range(X + 1):
			for j in range(Y + 1):
				for k in range(Z + 1):
					s = i + j + k
					total = 4 * i + 5 * j + 6 * k
					output = (output + total * fact[s - 1] * ons[s] * self.inverse(fact[i] * fact[j] * fact[k], rem)) % rem
		return output


class Solution:

	def getSum(self, x, y, z):
		s = [[[0] * (z + 1) for i in range(y + 1)] for j in range(x + 1)]
		n = [[[0] * (z + 1) for i in range(y + 1)] for j in range(x + 1)]
		n[0][0][0] = 1
		mod = 1000000007
		r = 0
		for i in range(x + 1):
			for j in range(y + 1):
				for k in range(z + 1):
					if i > 0:
						s[i][j][k] += (s[i - 1][j][k] * 10 + 4 * n[i - 1][j][k]) % mod
						n[i][j][k] += n[i - 1][j][k] % mod
					if j > 0:
						s[i][j][k] += (s[i][j - 1][k] * 10 + 5 * n[i][j - 1][k]) % mod
						n[i][j][k] += n[i][j - 1][k] % mod
					if k > 0:
						s[i][j][k] += (s[i][j][k - 1] * 10 + 6 * n[i][j][k - 1]) % mod
						n[i][j][k] += n[i][j][k - 1] % mod
					r += s[i][j][k] % mod
					r %= mod
		return r


mod = 1000000007

class Solution:

	def getSum(self, x, y, z):
		dp = [[[-1] * (z + 1) for j in range(y + 1)] for i in range(x + 1)]
		counter = [[[0] * (z + 1) for j in range(y + 1)] for i in range(x + 1)]
		total = 0
		dp[0][0][0] = 0
		if x > 0:
			dp[1][0][0] = 4
			counter[1][0][0] = 1
			total += 4
		if y > 0:
			dp[0][1][0] = 5
			counter[0][1][0] = 1
			total += 5
		if z > 0:
			dp[0][0][1] = 6
			counter[0][0][1] = 1
			total += 6
		for i in range(x + 1):
			for j in range(y + 1):
				for k in range(z + 1):
					if dp[i][j][k] == -1:
						summation = 0
						count = 0
						if i > 0:
							summation = (summation + dp[i - 1][j][k] * 10 % mod + 4 * counter[i - 1][j][k] % mod) % mod
							count = (count + counter[i - 1][j][k]) % mod
						if j > 0:
							summation = (summation + dp[i][j - 1][k] * 10 % mod + 5 * counter[i][j - 1][k] % mod) % mod
							count = (count + counter[i][j - 1][k]) % mod
						if k > 0:
							summation = (summation + dp[i][j][k - 1] * 10 % mod + 6 * counter[i][j][k - 1] % mod) % mod
							count = (count + counter[i][j][k - 1]) % mod
						dp[i][j][k] = summation
						counter[i][j][k] = count
						total = (total + dp[i][j][k]) % mod
		return total


class Solution:

	def getSum(self, x, y, z):
		mem = {}
		self.f_ans = 0

		def fun(x, y, z):
			if x == 0 and y == 0 and (z == 0):
				return (1, 0)
			if (x, y, z) in mem:
				return mem[x, y, z]
			ans = 0
			c = 0
			if x > 0:
				(m, n) = fun(x - 1, y, z)
				ans += m * 4 + n * 10
				c += m
			if y > 0:
				(m, n) = fun(x, y - 1, z)
				ans += m * 5 + n * 10
				c += m
			if z > 0:
				(m, n) = fun(x, y, z - 1)
				ans += m * 6 + n * 10
				c += m
			mem[x, y, z] = (c, ans)
			self.f_ans = (self.f_ans + ans) % 1000000007
			return (c, ans)
		fun(x, y, z)
		return self.f_ans


class Solution:

	def getSum(self, X, Y, Z):
		mat = [[[0] * (Z + 1) for _ in range(Y + 1)] for _ in range(X + 1)]
		num = [[[0] * (Z + 1) for _ in range(Y + 1)] for _ in range(X + 1)]
		num[0][0][0] = 1
		MOD = 10 ** 9 + 7
		res = 0
		for x in range(X + 1):
			for y in range(Y + 1):
				for z in range(Z + 1):
					if x:
						mat[x][y][z] += (10 * mat[x - 1][y][z] + 4 * num[x - 1][y][z]) % MOD
						num[x][y][z] += num[x - 1][y][z] % MOD
					if y:
						mat[x][y][z] += (10 * mat[x][y - 1][z] + 5 * num[x][y - 1][z]) % MOD
						num[x][y][z] += num[x][y - 1][z] % MOD
					if z:
						mat[x][y][z] += (10 * mat[x][y][z - 1] + 6 * num[x][y][z - 1]) % MOD
						num[x][y][z] += num[x][y][z - 1] % MOD
					res += mat[x][y][z] % MOD % MOD
		return res % MOD


from math import factorial

class Solution:

	def __init__(self):
		self.p = 10 ** 9 + 7

	def inverseModP(self, d, cache={}):
		if d in cache:
			return cache[d]
		if d == 1:
			return 1
		rlist = [self.p, d]
		alist = []
		while rlist[-1] > 1:
			r0 = rlist[-2]
			r1 = rlist[-1]
			alist.append(r0 // r1)
			rlist.append(r0 % r1)
		an = alist.pop()
		if not alist:
			return -an
		rcoeffs = [1, -an]
		while alist:
			(c1, c2) = rcoeffs
			rcoeffs[0] = c2
			rcoeffs[1] = c1 - c2 * alist.pop()
		cache[d] = rcoeffs[1]
		return rcoeffs[1]

	def getAllOnes(self, k, cache={}):
		if k in cache:
			return cache[k]
		c = 0
		for i in range(k):
			c = (10 * c + 1) % self.p
		c % self.p
		cache[k] = c
		return c

	def factorialMod(self, m, n, cache={}):
		if (m, n) in cache:
			return cache[m, n]
		f = 1
		for i in range(m, n + 1):
			f = f * i % self.p
		cache[m, n] = f
		return f

	def getSumFullDigits(self, X, Y, Z):
		if X == 0 and Y == 0 and (Z == 0):
			return 0
		k = X + Y + Z
		num = 1
		d1 = 1
		d2 = 1
		maxXYZ = max(X, Y, Z)
		if X == maxXYZ:
			num = self.factorialMod(X, k - 1)
			d1 = self.factorialMod(1, Y)
			d2 = self.factorialMod(1, Z)
			d3 = X
		elif Y == maxXYZ:
			num = self.factorialMod(Y, k - 1)
			d1 = self.factorialMod(1, X)
			d2 = self.factorialMod(1, Z)
			d3 = Y
		else:
			num = self.factorialMod(Z, k - 1)
			d1 = self.factorialMod(1, Y)
			d2 = self.factorialMod(1, X)
			d3 = Z
		denom = d1 * d2 * d3 % self.p
		dinv = self.inverseModP(denom)
		a = num * dinv % self.p
		b = (4 * X + 5 * Y + 6 * Z) % self.p
		c = self.getAllOnes(k)
		s = a * b * c % self.p
		return s

	def getSum(self, X, Y, Z):
		s = 0
		for x in range(X + 1):
			for y in range(Y + 1):
				for z in range(Z + 1):
					s += self.getSumFullDigits(x, y, z)
					s %= self.p
		return int(s)


from itertools import product
MOD = 10 ** 9 + 7

class Solution:

	def getSum(self, X, Y, Z):
		dp1 = [[[-1 for i in range(Z + 1)] for i in range(Y + 1)] for i in range(X + 1)]
		dp2 = [[[-1 for i in range(Z + 1)] for i in range(Y + 1)] for i in range(X + 1)]
		ans = [0]

		def count(i, j, k):
			if i == 0 and j == 0 and (k == 0):
				return 1
			if i < 0 or j < 0 or k < 0:
				return 0
			if dp2[i][j][k] != -1:
				return dp2[i][j][k]
			dp2[i][j][k] = 0
			res = 0
			res += count(i - 1, j, k) + count(i, j - 1, k) + count(i, j, k - 1)
			dp2[i][j][k] = res
			return res

		def solve(i, j, k):
			if i < 0 or j < 0 or k < 0:
				return 0
			if i == 0 and j == 0 and (k == 0):
				return 0
			if dp1[i][j][k] != -1:
				return dp1[i][j][k]
			dp1[i][j][k] = 0
			res = 0
			res += solve(i - 1, j, k) * 10 + count(i - 1, j, k) * 4
			res += solve(i, j - 1, k) * 10 + count(i, j - 1, k) * 5
			res += solve(i, j, k - 1) * 10 + count(i, j, k - 1) * 6
			dp1[i][j][k] = res
			ans[0] += res
			return res
		solve(X, Y, Z)
		return ans[0] % (10 ** 9 + 7)


class Solution:

	def getSum(self, x, y, z):
		dp = [[[0 for i in range(z + 1)] for i in range(y + 1)] for i in range(x + 1)]
		dp[0][0][0] = 0
		num = [[[0 for i in range(z + 1)] for i in range(y + 1)] for i in range(x + 1)]
		num[0][0][0] = 1
		ans = 0
		for i in range(x + 1):
			for j in range(y + 1):
				for k in range(z + 1):
					if i > 0:
						dp[i][j][k] += dp[i - 1][j][k] * 10 + num[i - 1][j][k] * 4
						dp[i][j][k] %= 10 ** 9 + 7
						num[i][j][k] += num[i - 1][j][k]
					if j > 0:
						dp[i][j][k] += dp[i][j - 1][k] * 10 + num[i][j - 1][k] * 5
						dp[i][j][k] %= 10 ** 9 + 7
						num[i][j][k] += num[i][j - 1][k]
					if k > 0:
						dp[i][j][k] += dp[i][j][k - 1] * 10 + num[i][j][k - 1] * 6
						dp[i][j][k] %= 10 ** 9 + 7
						num[i][j][k] += num[i][j][k - 1]
					ans += dp[i][j][k]
					ans %= 10 ** 9 + 7
		return ans


class Solution:

	def getSum(self, X, Y, Z):
		dicts = {(0, 0, 0): 0}
		cout = {(0, 0, 0): 1}
		ans = [0]

		def count(i, j, k):
			if (i, j, k) in cout:
				return cout[i, j, k]
			else:
				asd = asd1 = asd2 = 0
				if i > 0:
					asd = count(i - 1, j, k)
				if j > 0:
					asd1 = count(i, j - 1, k)
				if k > 0:
					asd2 = count(i, j, k - 1)
				cout[i, j, k] = asd + asd2 + asd1
				return cout[i, j, k]

		def func(x, y, z):
			if (x, y, z) in dicts:
				return dicts[x, y, z]
			asd = asd1 = asd2 = 0
			if x > 0:
				asd = func(x - 1, y, z) * 10 + 4 * count(x - 1, y, z)
			if y > 0:
				asd1 = func(x, y - 1, z) * 10 + 5 * count(x, y - 1, z)
			if z > 0:
				asd2 = func(x, y, z - 1) * 10 + 6 * count(x, y, z - 1)
			dicts[x, y, z] = asd + asd1 + asd2
			ans[0] += dicts[x, y, z]
			ans[0] %= 10 ** 9 + 7
			return dicts[x, y, z]
		func(X, Y, Z)
		return ans[0]