Given two strings S and T of length n and m respectively. Find count of distinct occurrences of T in S as a sub-sequence. 
 
Example 1:
Input:
S = "banana" , T = "ban"
Output: 3
Explanation: There are 3 sub-sequences:
[ban], [ba n], [b an].
Example 2:
Input:
S = "geeksforgeeks" , T = "ge"
Output: 6
Explanation: There are 6 sub-sequences:
[ge], [ ge], [g e], [g e] [g e] and [ g e].
Your Task:
You don't need to read input or print anything.Your task is to complete the function subsequenceCount() which takes two strings as argument S and T and returns the count of the sub-sequences modulo 10^{9} + 7.
Expected Time Complexity: O(n*m).
Expected Auxiliary Space: O(n*m).
Constraints:
1 ≤ length of(T) ≤ 100
1 ≤ length of(S) ≤ 8000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: # Your task is to complete this function

# Finction should return Integer

class Solution:

    def sequenceCount(self,arr1, arr2):

        # Code here

Solutions:
class Solution:

	def sequenceCount(self, arr1, arr2):
		n = len(arr1)
		m = len(arr2)
		if n < m:
			return 0
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				p1 = dp[i - 1][j]
				p2 = 0
				if arr1[i - 1] == arr2[j - 1]:
					p2 = dp[i - 1][j - 1]
				dp[i][j] = (p1 + p2) % 1000000007
		return dp[n][m]


class Solution:

	def sequenceCount(self, arr1, arr2):
		mod = 1000000000.0 + 7

		def f(i, j, a1, a2, dp):
			if j < 0:
				return 1
			if i < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if a1[i] == a2[j]:
				dp[i][j] = f(i - 1, j - 1, a1, a2, dp) + f(i - 1, j, a1, a2, dp)
				return int(dp[i][j] % mod)
			dp[i][j] = f(i - 1, j, a1, a2, dp)
			return int(dp[i][j] % mod)
		n = len(arr1)
		m = len(arr2)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if arr1[i - 1] == arr2[j - 1]:
					dp[i][j] = int((dp[i - 1][j - 1] + dp[i - 1][j]) % mod)
				else:
					dp[i][j] = int(dp[i - 1][j] % mod)
		return int(dp[n][m] % mod)


class Solution:

	def sequenceCount(self, arr1, arr2):
		n = len(arr1)
		m = len(arr2)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		return self.helper(n - 1, m - 1, n, m, arr1, arr2, dp)

	def helper(self, ind1, ind2, n, m, s1, s2, dp):
		mod = 10 ** 9 + 7
		if ind2 < 0:
			return 1
		if ind1 < 0:
			return 0
		if dp[ind1][ind2] != -1:
			return dp[ind1][ind2]
		if s1[ind1] == s2[ind2]:
			way1 = self.helper(ind1 - 1, ind2 - 1, n, m, s1, s2, dp)
			way2 = self.helper(ind1 - 1, ind2, n, m, s1, s2, dp)
			dp[ind1][ind2] = way1 + way2
		else:
			dp[ind1][ind2] = self.helper(ind1 - 1, ind2, n, m, s1, s2, dp)
		return dp[ind1][ind2] % mod


class Solution:

	def sequenceCount(self, s, t):
		n = len(s)
		m = len(t)
		front = [0] * (m + 1)
		front[-1] = 1
		for i in range(n - 1, -1, -1):
			curr = [0] * (m + 1)
			curr[-1] = 1
			for j in range(m - 1, -1, -1):
				pick = 0
				if s[i] == t[j]:
					pick = front[j + 1]
				notPick = front[j]
				curr[j] = (pick + notPick) % 1000000007
			front = curr
		return curr[0]


class Solution:

	def sequenceCount(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][m] = 1
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				pick = 0
				if s[i] == t[j]:
					pick = dp[i + 1][j + 1]
				notPick = dp[i + 1][j]
				dp[i][j] = (pick + notPick) % 1000000007
		return dp[0][0]


class Solution:

	def sequenceCount(self, arr1, arr2):
		n = len(arr1)
		m = len(arr2)
		M = 1000000007
		dp = [[-1 for i in range(m)] for i in range(n)]

		def f(i, j, dp):
			if j < 0:
				return 1
			if i < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if arr1[i] == arr2[j]:
				dp[i][j] = f(i - 1, j - 1, dp) + f(i - 1, j, dp)
			else:
				dp[i][j] = f(i - 1, j, dp)
			return dp[i][j]
		ans = f(len(arr1) - 1, len(arr2) - 1, dp) % M
		return ans


class Solution:

	def fun(self, i1, i2, s1, s2, dp):
		if i2 == 0:
			return 1
		if i1 == 0:
			return 0
		if dp[i1][i2] != -1:
			return dp[i1][i2] % (10 ** 9 + 7)
		if s1[i1 - 1] == s2[i2 - 1]:
			dp[i1][i2] = self.fun(i1 - 1, i2 - 1, s1, s2, dp) + self.fun(i1 - 1, i2, s1, s2, dp)
			return dp[i1][i2] % (10 ** 9 + 7)
		else:
			dp[i1][i2] = self.fun(i1 - 1, i2, s1, s2, dp)
			return dp[i1][i2] % (10 ** 9 + 7)

	def sequenceCount(self, s1, s2):
		(n, m) = (len(s1), len(s2))
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i1 in range(n + 1):
			dp[i1][0] = 1
		for i2 in range(1, m + 1):
			dp[0][i2] = 0
		for i1 in range(1, n + 1):
			for i2 in range(1, m + 1):
				if s1[i1 - 1] == s2[i2 - 1]:
					dp[i1][i2] = (dp[i1 - 1][i2 - 1] + dp[i1 - 1][i2]) % (10 ** 9 + 7)
				else:
					dp[i1][i2] = dp[i1 - 1][i2] % (10 ** 9 + 7)
		return dp[n][m]


class Solution:

	def sequenceCount(self, arr1, arr2):
		dp = [[-1 for i in range(len(arr2) + 1)] for j in range(len(arr1) + 1)]
		(n, m) = (len(arr1), len(arr2))

		def recursive(n, m):
			nonlocal dp, arr1, arr2
			if m == 0:
				return 1
			if n == 0:
				return 0
			if dp[n][m] != -1:
				return dp[n][m]
			dp[n][m] = recursive(n - 1, m)
			if arr1[n - 1] == arr2[m - 1]:
				dp[n][m] += recursive(n - 1, m - 1)
			return dp[n][m] % 1000000007
		return recursive(n, m)


class Solution:

	def sequenceCount(self, arr1, arr2):
		S = arr1
		T = arr2
		n = len(arr1)
		m = len(arr2)
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		mod = 10 ** 9 + 7
		for i in range(m + 1):
			dp[i][0] = 0
		for j in range(n + 1):
			dp[0][j] = 1
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if T[i - 1] != S[j - 1]:
					dp[i][j] = dp[i][j - 1] % mod
				else:
					dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod
		return dp[m][n] % mod


from itertools import product

class Solution:

	def sequenceCount(self, s, t):
		cache = {}

		def dfs(i, j):
			if j == len(t):
				return 1
			if i == len(s):
				return 0
			if (i, j) in cache:
				return cache[i, j]
			if s[i] == t[j]:
				cache[i, j] = dfs(i + 1, j + 1) % (10 ** 9 + 7) + dfs(i + 1, j) % (10 ** 9 + 7)
			else:
				cache[i, j] = dfs(i + 1, j) % (10 ** 9 + 7)
			return cache[i, j]
		return dfs(0, 0) % (10 ** 9 + 7)


from itertools import product

class Solution:

	def sequenceCount(self, s, t):
		(m, n) = (len(s), len(t))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for i in range(m):
			dp[i][0] = 1
		for (i, j) in product(range(1, m + 1), range(1, n + 1)):
			if s[i - 1] == t[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
			else:
				dp[i][j] = dp[i - 1][j]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def sequenceCount(self, s, t):
		n = len(s)
		m = len(t)
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][m] % 1000000007


def fun(i, j, s1, s2, dp):
	if j < 0:
		return 1
	if i < 0:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	if s1[i] == s2[j]:
		dp[i][j] = (fun(i - 1, j - 1, s1, s2, dp) + fun(i - 1, j, s1, s2, dp)) % 1000000007
		return dp[i][j]
	else:
		dp[i][j] = fun(i - 1, j, s1, s2, dp) % 1000000007
		return dp[i][j]

class Solution:

	def sequenceCount(self, arr1, arr2):
		s1 = arr1
		s2 = arr2
		dp = [[-1] * len(s2) for i in range(len(s1))]
		return fun(len(s1) - 1, len(s2) - 1, s1, s2, dp)


class Solution:

	def sequenceCount(self, arr1, arr2):
		(n, m) = (len(arr1), len(arr2))
		t = [[-1 for i in range(m + 1)] for j in range(n + 1)]

		def solve(i, j):
			if j == m:
				return 1
			if i >= n:
				return 0
			if t[i][j] != -1:
				return t[i][j]
			if arr1[i] == arr2[j]:
				t[i][j] = solve(i + 1, j + 1) + solve(i + 1, j)
				return t[i][j]
			t[i][j] = solve(i + 1, j)
			return t[i][j]
		return solve(0, 0) % (10 ** 9 + 7)