Given string s consisting of digits 0-9 and a number N, the task is to count the number of subsequences that are divisible by N.
Note: Answer can be large, output answer modulo 10^{9} + 7
Example 1:
Input: s = "1234", N = 4
Output: 4
Explanation: The subsequences 4, 12, 24 and 
124 are divisible by 4.
Example 2:
Input: s = "330", N = 6
Output: 4
Explanation: The subsequences 30, 30, 330 
and 0 are divisible by 6.
Your Task:  
You don't need to read input or print anything. Complete the function countDivisibleSubseq() which takes s and N as input parameters and returns the integer value
Expected Time Complexity: O(|s|*N)
Expected Auxiliary Space: O(|s|*N)
Constraints:
1 ≤ |s|*N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def countDivisibleSubseq(self, s, N):
		# code here

Solutions:
class Solution:

	def countDivisibleSubseq(self, str, n):
		mod = int(1000000000.0 + 7)
		l = len(str)
		dp = [[0 for x in range(l)] for y in range(n)]
		dp[int(str[0]) % n][0] += 1
		for i in range(1, l):
			dp[int(str[i]) % n][i] += 1
			for j in range(n):
				dp[j][i] += dp[j][i - 1]
				dp[(j * 10 + int(str[i])) % n][i] += dp[j][i - 1]
		return dp[0][l - 1] % mod


class Solution:

	def countDivisibleSubseq(self, s, N):
		mod = int(1000000007)
		l = len(s)
		dp = [[0 for x in range(n)] for y in range(l)]
		for i in range(0, l):
			dp[i][int(s[i]) % N] = 1
			dp[i][int(s[i]) % N] = dp[i][int(s[i]) % N] % mod
		for i in range(1, l):
			for j in range(0, N):
				dp[i][j] += dp[i - 1][j]
				dp[i][j] = dp[i][j] % mod
				dp[i][(j * 10 + int(s[i])) % N] += dp[i - 1][j]
				dp[i][(j * 10 + int(s[i])) % N] = dp[i][(j * 10 + int(s[i])) % N] % mod
		return dp[l - 1][0] % mod


class Solution:

	def countDivisibleSubseq(self, s, N):
		MOD = 10 ** 9 + 7

		def rec(index, rem):
			if index == len(s):
				return int(rem == 0)
			nt = rec(index + 1, rem)
			tk = rec(index + 1, (rem * 10 + int(s[index])) % N)
			return nt + tk
		dp = [[-1 for _ in range(N + 1)] for _ in range(len(s) + 1)]

		def mem(index, rem):
			if index == len(s):
				return int(rem == 0)
			if dp[index][rem] != -1:
				return dp[index][rem]
			nt = mem(index + 1, rem)
			tk = mem(index + 1, (rem * 10 + int(s[index])) % N)
			dp[index][rem] = nt + tk
			return dp[index][rem]
		return mem(0, N) % MOD
		return rec(0, N) % MOD


class Solution:

	def countDivisibleSubseq(self, s, n):
		l = len(s)
		dp = [[0 for x in range(l)] for y in range(n)]
		dp[int(s[0]) % n][0] += 1
		for i in range(1, l):
			dp[int(s[i]) % n][i] += 1
			for j in range(n):
				dp[j][i] += dp[j][i - 1]
				dp[(j * 10 + int(s[i])) % n][i] += dp[j][i - 1]
		return dp[0][l - 1] % (7 + 10 ** 9)


class Solution:

	def countDivisibleSubseq(self, s, N):
		memo = {}
		s = str(s)
		return (getcount(s, 0, 0, N, memo) - 1) % (10 ** 9 + 7)

def getcount(s, idx, rem, k, memo):
	n = len(s)
	if idx == n:
		return 1 if rem == 0 else 0
	if hashed(idx, rem) in memo:
		return memo[hashed(idx, rem)]
	count = 0
	count += getcount(s, idx + 1, rem, k, memo)
	count += getcount(s, idx + 1, (rem * 10 + int(s[idx])) % k, k, memo)
	memo[hashed(idx, rem)] = count
	return count

def hashed(a, b):
	return str(a) + ':' + str(b)