You are given 5 integers - N,A,B,C,D.
Let us say all the integers of length N, having only A or B in their decimal representation are good integers. Also, among all the good integers, all those integers whose sum of digits should contains either C or D or both on it, are best integers.
Find the number of best integers of length N. Since the number of best integers can be huge, print it modulo 10^{9}+7.
Example 1:
Input:
N = 2, A = 1, B = 2, C = 3, D = 5
Output: 
2
Explanation: 
The following are good integers:- 
{ 12 , 22 , 11 , 21 }
And the following are best integers:- 
{ 12, 21 } because sum of digits 3 & 5
contains C & D, which is 3 as well as 5.
Example 2:
Input:
N = 1, A = 1, B = 1, C = 2, D = 3
Output: 
0
Explanation: 
The following are good integers: - { 1 }
Since sum of digits is 1 which does not contains
C or D, therefore, answer is 0.
Example 3:
Input:
N = 4, A = 6, B = 7, C = 5, D = 3
Output: 
4
Explanation: 
The following are good integers:- 
{ 6667 , 6676 , 6766 , 7666.....and many more}
out of all these four { 6667 , 6676 , 6766 , 7666}
is best number because sum of all these four 
numbers is 25, which contains C, which is 5.
Your Task:
The task is to complete the function solve() which takes five integers N,A,B,C and D as input parameters and returns the number of best integers modulo 10^{9}+7.
Expected Time Complexity: O(NlogN)
Expected Space Complexity: O(N)
Constraints:
1 ≤ A, B, C, D ≤ 9
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code: class Solution:

    def bestNumbers(self, N : int, A : int, B : int, C : int, D : int) -> int:

        # code here

        



Solutions:
def compute_factorial(N, MOD):
	fact = [1] * (N + 1)
	inv_fact = [1] * (N + 1)
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % MOD
		inv_fact[i] = pow(fact[i], MOD - 2, MOD)
	return (fact, inv_fact)

class Solution:
	MOD = 10 ** 9 + 7
	(fact, inv_fact) = compute_factorial(10 ** 5, MOD)

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		if A == B:
			S = set(map(int, str(A * N)))
			return int(C in S or D in S)
		res = 0
		for x in range(N + 1):
			y = N - x
			S = set(map(int, str(A * x + B * y)))
			if C in S or D in S:
				res = (res + Solution.fact[N] * Solution.inv_fact[x] * Solution.inv_fact[y]) % Solution.MOD
		return res


flag = 0
N = 10 ** 5 + 5
M = 10 ** 9 + 7
fact = [0] * N
invfact = [0] * N

def init():
	N = 10 ** 5 + 5
	fact[0] = 1
	for i in range(1, N):
		fact[i] = i * fact[i - 1] % M
	invfact[N - 1] = pow(fact[N - 1], M - 2, M)
	for i in range(N - 2, -1, -1):
		invfact[i] = (i + 1) * invfact[i + 1] % M

def ncr(n, r, p):
	ans = fact[n] * invfact[n - r] % p * invfact[r] % p
	return ans

class Solution:

	def bestNumbers(self, n: int, a: int, b: int, c: int, d: int) -> int:
		global flag
		if flag == 0:
			flag = 1
			init()
		ans = 0
		if a == b:
			Sum = n * a
			while Sum > 0:
				if Sum % 10 == c or Sum % 10 == d:
					return 1
				Sum = Sum // 10
			return 0
		for i in range(0, n + 1):
			Sum = i * a + (n - i) * b
			good = False
			while Sum > 0:
				if Sum % 10 == c or Sum % 10 == d:
					good = True
					break
				Sum = Sum // 10
			if good:
				ans += ncr(n, i, M)
				ans %= M
		return ans


from functools import lru_cache

@lru_cache()
def contains_digits(num: int, c: int, d: int) -> bool:
	while num > 0:
		ones = num % 10
		if ones == c or ones == d:
			return True
		num = num // 10
	return False
import operator as op
from functools import reduce
MODULUS = 10 ** 9 + 7

def compute_factorial(N, MOD):
	fact = [1] * (N + 1)
	inv_fact = [1] * (N + 1)
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % MOD
		inv_fact[i] = pow(fact[i], MOD - 2, MOD)
	return (fact, inv_fact)
(fact, inv_fact) = compute_factorial(10 ** 5, MODULUS)

def ncr_mod_p(n, r):
	n_fact = fact[n]
	inv_r_fact = inv_fact[r]
	inv_n_r_fact = inv_fact[n - r]
	res = n_fact * inv_r_fact % MODULUS
	res = res * inv_n_r_fact % MODULUS
	return res

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		if A == B:
			digit_sum = N * A
			if contains_digits(digit_sum, C, D):
				return 1
			else:
				return 0
		num_best_ints = 0
		C_str = str(C)
		D_str = str(D)
		for m in range(0, N + 1):
			n = N - m
			digit_sum = m * A + n * B
			if contains_digits(digit_sum, C, D):
				r = min(n, m)
				num_best_ints = (num_best_ints + ncr_mod_p(N, r)) % MODULUS
		return num_best_ints


flag = 0
N = 10 ** 5 + 5
M = 10 ** 9 + 7
fact = [0] * N
invfact = [0] * N

def init():
	N = 10 ** 5 + 5
	fact[0] = 1
	for i in range(1, N):
		fact[i] = i * fact[i - 1] % M
	invfact[N - 1] = pow(fact[N - 1], M - 2, M)
	for i in range(N - 2, -1, -1):
		invfact[i] = (i + 1) * invfact[i + 1] % M

def rouge_func(n, r, p):
	ans = fact[n] * invfact[n - r] % p * invfact[r] % p
	return ans

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		global flag
		if flag == 0:
			flag = 1
			init()
		ans = 0
		if A == B:
			Sum = N * A
			while Sum > 0:
				if Sum % 10 == C or Sum % 10 == D:
					return 1
				Sum = Sum // 10
			return 0
		for i in range(0, N + 1):
			Sum = i * A + (N - i) * B
			good = False
			while Sum > 0:
				if Sum % 10 == C or Sum % 10 == D:
					good = True
					break
				Sum = Sum // 10
			if good:
				ans += rouge_func(N, i, M)
				ans %= M
		return ans


mod = 10 ** 9 + 7

def binpow(a, n):
	ans = 1
	while n > 0:
		if n & 1:
			ans *= a % mod
		a *= a % mod
		n >>= 1
	return ans % mod

def inv(a):
	return binpow(a, mod - 2)
fact = [1]
n = 10 ** 5 + 6
inva = [0] * n
for i in range(1, n):
	fact.append(fact[-1] * i % mod)
inva[n - 1] = inv(fact[n - 1])
for i in range(n - 2, -1, -1):
	inva[i] = (i + 1) * inva[i + 1] % mod

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		ans = 0

		def ncr(n, r):
			ret = fact[n] * inva[r] % mod * inva[n - r] % mod
			return ret
		for i in range(N + 1):
			summ = i * A + (N - i) * B
			f = 0
			while summ > 0:
				digit = summ % 10
				if digit == C or digit == D:
					f = 1
					break
				summ //= 10
			if A == B:
				return f
			if f and A != B:
				ans += ncr(N, i)
				ans %= mod
		return ans


mod = int(1000000000.0) + 7
from functools import lru_cache

@lru_cache(None)
def binPower(a, n):
	res = 1
	while n > 0:
		if n % 2 != 0:
			res = res * a % mod
		a = a * a % mod
		n //= 2
	return res

@lru_cache(None)
def ncr(n, r):
	if r == 0 or r == n:
		return 1
	return (ncr(n - 1, r - 1) + ncr(n - 1, r)) % mod

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		if A == B:
			if str(C) in str(N * A) or str(D) in str(N * A):
				return 1
			return 0
		fact = [0] * (N + 1)
		fact[0] = 1
		for i in range(1, N + 1):
			fact[i] = fact[i - 1] * i % mod
		ans = 0
		for i in range(N + 1):
			sum = i * A + (N - i) * B
			if str(C) in str(sum) or str(D) in str(sum):
				ans += fact[N] * binPower(fact[i] * fact[N - i] % mod, mod - 2)
				ans %= mod
		return int(ans)


class Solution:

	def check(self, n: int, c: int, d: int) -> bool:
		while n:
			r = n % 10
			if r == c or r == d:
				return True
			n //= 10
		return False

	def binpow(self, a: int, b: int, mod: int) -> int:
		res = 1
		while b:
			if b & 1:
				res = res * a % mod
			a = a * a % mod
			b >>= 1
		return res

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		if A == B:
			return int(self.check(N * A, C, D))
		mod = int(1000000000.0 + 7)
		ans = 0
		fac = [0] * (N + 1)
		fac[0] = 1
		for i in range(1, N + 1):
			fac[i] = fac[i - 1] * i % mod
		inv_fac = [0] * (N + 1)
		inv_fac[N] = pow(fac[N], mod - 2, mod)
		for i in range(N, 0, -1):
			inv_fac[i - 1] = inv_fac[i] * i % mod
		for i in range(N + 1):
			s = i * A + (N - i) * B
			if self.check(s, C, D):
				ans = (ans + fac[N] * inv_fac[i] * inv_fac[N - i] % mod) % mod
		return ans


done = 0
f = []
inv = []
M = int(1000000000.0) + 7

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		global done, f, inv
		if not done:
			self.pre()
		if A == B:
			sum_val = N * A
			flag = False
			while sum_val > 0:
				if sum_val % 10 == C or sum_val % 10 == D:
					flag = True
					break
				sum_val //= 10
			if flag:
				return 1
			else:
				return 0
		ans = 0
		for i in range(N + 1):
			sum_val = i * A + (N - i) * B
			flag = False
			while sum_val > 0:
				if sum_val % 10 == C or sum_val % 10 == D:
					flag = True
					break
				sum_val //= 10
			if flag:
				ans = (ans + self.nCr(N, i)) % M
		return ans

	def pre(self):
		global done, f, inv
		done = 1
		f = [1] * (int(100000.0) + 1)
		inv = [0] * (int(100000.0) + 1)
		for i in range(2, int(100000.0) + 1):
			f[i] = f[i - 1] * i % M
		inv[int(100000.0)] = self.fastpow(f[int(100000.0)], M - 2)
		for i in range(int(100000.0) - 1, -1, -1):
			inv[i] = inv[i + 1] * (i + 1) % M

	def fastpow(self, a: int, n: int) -> int:
		res = 1
		while n > 0:
			if n & 1:
				res = res * a % M
			a = a * a % M
			n >>= 1
		return res

	def nCr(self, n: int, r: int) -> int:
		return f[n] * inv[n - r] % M * inv[r] % M


from math import factorial
N = 10 ** 5
MOD = 10 ** 9 + 7
fact = [1] * (N + 1)
inv_fact = [1] * (N + 1)
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % MOD
	inv_fact[i] = pow(fact[i], MOD - 2, MOD)

class Solution:

	def bestNumbers(self, n: int, a: int, b: int, c: int, d: int) -> int:
		mod = 10 ** 9 + 7
		(c, d) = (str(c), str(d))
		if a == b:
			cur = str(n * a)
			if c in cur or d in cur:
				return 1
			else:
				return 0
		ncr = lambda n, r: fact[n] // (fact[r] * fact[n - r]) % mod
		res = 0
		for x in range(n + 1):
			y = n - x
			cur = str(x * a + y * b)
			if c in cur or d in cur:
				res += fact[N] * inv_fact[x] * inv_fact[y]
				res %= mod
		return res % mod


N = 10 ** 5 + 5
mod = 10 ** 9 + 7
fact = [0] * N
inv_fact = [0] * N
flag = 0

def init():
	N = 10 ** 5 + 5
	fact[0] = 1
	for i in range(1, N):
		fact[i] = i * fact[i - 1] % mod
	inv_fact[N - 1] = pow(fact[N - 1], mod - 2, mod)
	for i in range(N - 2, -1, -1):
		inv_fact[i] = (i + 1) * inv_fact[i + 1] % mod

def nCr(n, r, m):
	ans = fact[n] * inv_fact[n - r] % m * inv_fact[r] % m
	return ans

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		global flag
		if flag == 0:
			flag = 1
			init()
		ans = 0
		if A == B:
			sum = N * A
			while sum > 0:
				if sum % 10 == C or sum % 10 == D:
					return 1
				sum = sum // 10
			return 0
		for i in range(0, N + 1):
			sum = i * A + (N - i) * B
			good = False
			while sum > 0:
				if sum % 10 == C or sum % 10 == D:
					good = True
					break
				sum = sum // 10
			if good:
				ans = (ans + nCr(N, i, mod)) % mod
		return ans


import math
MOD = 10 ** 9 + 7
FACTORIAL = [1, 1]
INVFACT = [1, 1]
NMAX = 10 ** 5
k = kf = 1
while k < NMAX:
	k += 1
	kf = kf * k % MOD
	FACTORIAL.append(kf)
	INVFACT.append(pow(kf, MOD - 2, MOD))

def comb(n, k):
	if 0 <= k <= n:
		return FACTORIAL[n] * INVFACT[k] * INVFACT[n - k] % MOD
	else:
		return 0

class Solution:

	def bestNumbers(self, N: int, A: int, B: int, C: int, D: int) -> int:
		cddig = str(C) + str(D)
		if A == B:
			return int(any((c in cddig for c in str(N * A))))
		result = 0
		for k in range(N + 1):
			dsum = k * B + (N - k) * A
			if any((d in cddig for d in str(dsum))):
				result = (result + comb(N, k)) % MOD
		return result