Given two strings S1 and S2, Count no. of all subsequences of string S1 that are equal to string S2.
Example 1:
Input: 
S1 = geeksforgeeks
S2 = gks
Output: 4
Explaination: We can pick characters from S1 as a subsequence from indices {0,3,4}, {0,3,12}, {0,11,12} and {8,11,12}.So total 4 subsequences of S1 that are equal to S2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countWays() which takes the string S1 and S2 as input parameters and returns the number of desired subsequences.
Expected Time Complexity: O(n*m)        [n and m are length of the strings]
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n, m ≤ 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def countWays(self, S1, S2):
        # code here 

Solutions:
class Solution:

	def countWays(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = [[-1 for i in range(m)] for j in range(n)]

		def answer(i, j):
			if j == -1:
				return 1
			if i == -1:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if s1[i] == s2[j]:
				dp[i][j] = answer(i - 1, j - 1) + answer(i - 1, j)
			else:
				dp[i][j] = answer(i - 1, j)
			return dp[i][j]
		return answer(n - 1, m - 1)


class Solution:

	def get(self, i, j, n, m, s1, s2, dp):
		if j == m:
			return 1
		elif i == n:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		ans = 0
		if s1[i] == s2[j]:
			ans = self.get(i + 1, j + 1, n, m, s1, s2, dp)
		ans += self.get(i + 1, j, n, m, s1, s2, dp)
		dp[i][j] = ans
		return ans

	def countWays(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = []
		for i in range(0, n + 1):
			dp.append([-1 for i in range(0, m + 1)])
		return self.get(0, 0, n, m, s1, s2, dp)


from itertools import product

class Solution:

	def countWays(self, s, t):
		(m, n) = (len(s), len(t))
		dp = [[0] * (n + 1) for _ in range(m + 1)]
		for row in range(m + 1):
			dp[row][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]


class Solution:

	def solve(self, s1, s2, m, n):
		dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
		for i in range(m + 1):
			dp[i][0] = 1
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[m][n]

	def countWays(self, S1, S2):
		return self.solve(S1, S2, len(S1), len(S2))


class Solution:

	def countWays(self, S1, S2):
		m = len(S1)
		n = len(S2)
		lookup = [[0] * (n + 1) for i in range(m + 1)]
		for i in range(n + 1):
			lookup[0][i] = 0
		for i in range(m + 1):
			lookup[i][0] = 1
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				if S1[i - 1] == S2[j - 1]:
					lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j]
				else:
					lookup[i][j] = lookup[i - 1][j]
		return lookup[m][n]


class Solution:

	def countWays(self, S1, S2):
		count = 0
		l1 = len(S1)
		l2 = len(S2)
		i1 = 0
		i2 = 0
		a = list()
		while 1:
			if i1 == l1:
				if len(a) == 0:
					break
				i1 = a.pop() + 1
				i2 -= 1
				continue
			if S1[i1] == S2[i2]:
				if i2 == l2 - 1:
					count += 1
				else:
					a.append(i1)
					i2 += 1
			i1 += 1
		return count


class Solution:

	def countWays(self, s, t):
		dp = {}

		def fun(n, m):
			if n > 0 and m == 0:
				return 1
			if n == 0 and m > 0:
				return 0
			if n == 0 and m == 0:
				return 1
			if (n, m) in dp:
				return dp[n, m]
			if s[n - 1] == t[m - 1]:
				dp[n, m] = fun(n - 1, m - 1) + fun(n - 1, m)
			else:
				dp[n, m] = fun(n - 1, m)
			return dp[n, m]
		return fun(len(s), len(t))


class Solution:

	def countWays(self, S1, S2):
		n = len(S1)
		m = len(S2)

		def f(i, j, s1, s2):
			if j < 0:
				return 1
			if i < 0:
				return 0
			if s1[i] == s2[j]:
				return f(i - 1, j, s1, s2) + f(i - 1, j - 1, s1, s2)
			else:
				return f(i - 1, j, s1, s2)
		return f(n - 1, m - 1, S1, S2)


from collections import defaultdict

class Solution:

	def countWays(self, S1, S2):
		dp = [0] * (len(S2) + 1)
		dp[-1] = 1
		mp = defaultdict(list)
		for (i, x) in enumerate(S2):
			mp[x].append(i)
		for i in reversed(range(len(S1))):
			for j in mp[S1[i]]:
				dp[j] += dp[j + 1]
		return dp[0]


class Solution:

	def countWays(self, s1, s2):
		(l1, l2) = (len(s1), len(s2))

		def solve(s1, s2, i, j):
			if i == 0 and j == 0 or j == 0:
				return 1
			if i == 0:
				return 0
			temp = solve(s1, s2, i - 1, j)
			if s1[i - 1] == s2[j - 1]:
				temp += solve(s1, s2, i - 1, j - 1)
			return temp
		return solve(s1, s2, l1, l2)


class Solution:

	def countWays(self, S1, S2):

		def solve(s1, s2, i, j):
			if i == 0 and j == 0 or j == 0:
				return 1
			if i == 0:
				return 0
			if s1[i - 1] == s2[j - 1]:
				return solve(s1, s2, i - 1, j - 1) + solve(s1, s2, i - 1, j)
			else:
				return solve(s1, s2, i - 1, j)
		return solve(S1, S2, len(S1), len(S2))


class Solution:

	def countWays(self, S1, S2):
		s1_len = len(S1)
		s2_len = len(S2)
		dp = [[0] * (s2_len + 1) for _ in range(s1_len + 1)]
		for i in range(s1_len + 1):
			dp[i][0] = 1
		for i in range(1, s1_len + 1):
			for j in range(1, s2_len + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[i][j]


class Solution:

	def countWays(self, s1, s2):
		(m, n) = (len(s1), len(s2))
		dp = dict()

		def f(i, j):
			if j >= n:
				return 1
			if i >= m:
				return 0
			if (i, j) not in dp:
				if s1[i] == s2[j]:
					dp[i, j] = f(i + 1, j + 1) + f(i + 1, j)
				else:
					dp[i, j] = f(i + 1, j)
			return dp[i, j]
		return f(0, 0)


class Solution:

	def countWays(self, S1, S2):
		m = len(S1)
		n = len(S2)
		dp = []
		for i in range(m + 1):
			dp.append([0] * (n + 1))
			dp[0][0] = 1
		for i in range(m + 1):
			for j in range(n + 1):
				if j == 0:
					dp[i][0] = 1
				elif i == 0:
					dp[0][j] = 0
				elif S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				elif S1[i - 1] != S2[j - 1]:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def countWays(self, s1, s2):
		matrix = [[-1 for i in range(0, len(s2) + 1)] for j in range(0, len(s1) + 1)]
		for i in range(0, len(s1) + 1):
			for j in range(0, len(s2) + 1):
				if j == 0:
					matrix[i][j] = 1
				elif i == 0:
					matrix[i][j] = 0
				elif s1[i - 1] == s2[j - 1]:
					matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1]
				else:
					matrix[i][j] = matrix[i - 1][j]
		return matrix[-1][-1]


def f(A, B, i, j, dp):
	if j == len(B) and i <= len(A):
		return 1
	if i == len(A) or j == len(B):
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	ans = 0
	if A[i] == B[j]:
		ans += f(A, B, i + 1, j + 1, dp)
	ans += f(A, B, i + 1, j, dp)
	dp[i][j] = ans
	return ans

class Solution:

	def countWays(self, S1, S2):
		dp = [[-1 for i in range(501)] for i in range(501)]
		return f(S1, S2, 0, 0, dp)


class Solution:

	def countWays(self, s1, s2):
		x = len(s1)
		y = len(s2)
		l = [[0 for i in range(y + 1)] for j in range(x + 1)]
		for i in range(x + 1):
			for j in range(y + 1):
				if j == 0:
					l[i][j] = 1
				elif i == 0:
					continue
				elif s1[i - 1] == s2[j - 1]:
					l[i][j] = l[i - 1][j - 1] + l[i - 1][j]
				else:
					l[i][j] = l[i - 1][j]
		return l[x][y]


import functools

class Solution:

	def countWays(self, s1, s2):
		m = len(s1)
		n = len(s2)

		@functools.lru_cache(maxsize=None)
		def count(s1, s2, m, n):
			if n == 0:
				return 1
			if m == 0:
				return 0
			if s1[m - 1] == s2[n - 1]:
				return count(s1, s2, m - 1, n - 1) + count(s1, s2, m - 1, n)
			else:
				return count(s1, s2, m - 1, n)
		return count(s1, s2, m, n)


class Solution:

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

	def countWays(self, S1, S2):

		def f(s1, s2, m, n):
			if (m == 0 or m > 0) and n == 0:
				return 1
			if m == 0:
				return 0
			x = 0
			if (m, n) in self.d.keys():
				return self.d[m, n]
			if s1[m - 1] == s2[n - 1]:
				x = f(s1, s2, m - 1, n - 1) + f(s1, s2, m - 1, n)
			else:
				x = f(s1, s2, m - 1, n)
			self.d[m, n] = x
			return x
		return f(S1, S2, len(S1), len(S2))


class Solution:

	def countWays(self, S1, S2):

		def f(s1, s2, m, n):
			if (m == 0 or m > 0) and n == 0:
				return 1
			if m == 0:
				return 0
			x = 0
			if s1[m - 1] == s2[n - 1]:
				x = f(s1, s2, m - 1, n - 1) + f(s1, s2, m - 1, n)
			else:
				x = f(s1, s2, m - 1, n)
			return x
		return f(S1, S2, len(S1), len(S2))


class Solution:

	def countWays(self, s, t):
		s_len = len(s)
		t_len = len(t)
		dp = [[0 for _ in range(1 + t_len)] for _ in range(1 + s_len)]
		for i in range(1 + s_len):
			dp[i][0] = 1
		for i in range(1, 1 + s_len):
			for j in range(1, 1 + t_len):
				if s[i - 1] == t[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				elif s[i - 1] != t[j - 1]:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def countWays(self, S1, S2):
		a = len(S1)
		b = len(S2)
		dp = [[0] * (b + 1) for i in range(a + 1)]
		for i in range(0, len(dp)):
			dp[i][0] = 1
		for i in range(1, a + 1):
			for j in range(1, b + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[a][b]


class Solution:

	def countWays(self, S1, S2):
		N1 = len(S1)
		N2 = len(S2)
		dp = [[0 for i in range(N2 + 1)] for j in range(N1 + 1)]
		for i in range(N2 + 1):
			dp[0][i] = 0
		for i in range(N1 + 1):
			dp[i][0] = 1
		for i in range(1, N1 + 1):
			for j in range(1, N2 + 1):
				if S1[i - 1] == S2[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]


class Solution:

	def countWays(self, S1, S2):

		def solve(i, j):
			if j == len(S2):
				return 1
			if i >= len(S1):
				return 0
			if S1[i] == S2[j]:
				return solve(i + 1, j + 1) + solve(i + 1, j)
			else:
				return solve(i + 1, j)
		return solve(0, 0)


class Solution:

	def countWays(self, s1, s2):
		(n1, n2) = (len(s1), len(s2))
		dp = [[0] * (n1 + 1) for i in range(n2 + 1)]
		dp[0] = [1] * (n1 + 1)
		for i in range(1, n2 + 1):
			for j in range(1, n1 + 1):
				dp[i][j] = dp[i][j - 1]
				if s1[j - 1] == s2[i - 1]:
					dp[i][j] += dp[i - 1][j - 1]
		return dp[-1][-1]


from functools import lru_cache

class Solution:

	def countWays(self, S1, S2):
		(m, n) = (len(S1), len(S2))

		@lru_cache(None)
		def helper(i=0, j=0):
			if j == n:
				return 1
			if i == m:
				return 0
			res = 0
			if S1[i] == S2[j]:
				res += helper(i + 1, j + 1) + helper(i + 1, j)
			else:
				res += helper(i + 1, j)
			return res
		return helper()


class Solution:

	def countWays(self, S1, S2):
		(m, n) = (len(S1), len(S2))

		def helper(i=0, j=0):
			if j == n:
				return 1
			if i == m:
				return 0
			res = 0
			if S1[i] == S2[j]:
				res += helper(i + 1, j + 1) + helper(i + 1, j)
			else:
				res += helper(i + 1, j)
			return res
		return helper()


class Solution:

	def countWays(self, s1, s2):

		def fun(s1, s2, m, n):
			if m == 0 and n == 0:
				return 1
			if m == 0:
				return 0
			if n == 0:
				return 1
			if s1[m - 1] == s2[n - 1]:
				return fun(s1, s2, m - 1, n) + fun(s1, s2, m - 1, n - 1)
			else:
				return fun(s1, s2, m - 1, n)
		return fun(s1, s2, len(s1), len(s2))


class Solution:

	def countWays(self, S1, S2):

		def solve(m, n):
			if m == 0 and n == 0 or n == 0:
				return 1
			if m == 0:
				return 0
			if (m, n) in d:
				return d[m, n]
			if S1[m - 1] == S2[n - 1]:
				d[m, n] = solve(m - 1, n - 1) + solve(m - 1, n)
			else:
				d[m, n] = solve(m - 1, n)
			return d[m, n]
		m = len(S1)
		n = len(S2)
		d = {}
		return solve(m, n)


class Solution:

	def solve(self, s1, s2, ind1, ind2):
		if ind1 < 0 and ind2 < 0 or ind2 < 0:
			return 1
		if ind1 < 0:
			return 0
		if s1[ind1] == s2[ind2]:
			return self.solve(s1, s2, ind1 - 1, ind2 - 1) + self.solve(s1, s2, ind1 - 1, ind2)
		else:
			return self.solve(s1, s2, ind1 - 1, ind2)

	def countWays(self, S1, S2):
		return self.solve(S1, S2, len(S1) - 1, len(S2) - 1)


class Solution:

	def countWays(self, S1, S2):
		l1 = len(S1)
		l2 = len(S2)
		dp = [[0] * (l2 + 1) for i in range(l1 + 1)]
		for i in range(l1 + 1):
			dp[i][0] = 1
		for i in range(1, l2 + 1):
			dp[0][i] = 0
		for i in range(1, l1 + 1):
			for j in range(1, l2 + 1):
				if S1[i - 1] == S2[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]


class Solution:

	def count(self, a, b, m, n):
		if m == 0 and n == 0 or n == 0:
			return 1
		if m == 0:
			return 0
		if a[m - 1] == b[n - 1]:
			return self.count(a, b, m - 1, n - 1) + self.count(a, b, m - 1, n)
		else:
			return self.count(a, b, m - 1, n)

	def countWays(self, S, P):
		res = self.count(S, P, len(S), len(P))
		return res
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def countWays(self, S1, S2):
		n = len(S1)
		m = len(S2)
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0:
					dp[i][j] = 0
				if i == 0 and j == 0 or j == 0:
					dp[i][j] = 1
				elif S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n][m]
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def countWays(self, S1, S2):
		(len_1, len_2) = (len(S1), len(S2))
		count = [0 for _ in range(len_2)]
		for i1 in range(len_1):
			for i2 in range(len_2 - 1, -1, -1):
				if S1[i1] == S2[i2]:
					if i2:
						count[i2] += count[i2 - 1]
					else:
						count[i2] += 1
		return count[len_2 - 1]
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def countWays(self, s1, s2):
		n = len(s1)
		m = len(s2)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]

		def recur(n, m):
			if m == 0:
				return 1
			if n == 0:
				return 0
			if dp[n][m] != -1:
				return dp[n][m]
			res = 0
			if s2[m - 1] == s1[n - 1]:
				res += recur(n - 1, m - 1)
			res += recur(n - 1, m)
			dp[n][m] = res
			return res
		return recur(n, m)
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def recur(self, ind1, ind2, s1, s2):
		global dp
		if ind2 == -1:
			return 1
		if ind1 == -1:
			return 0
		if dp[ind1][ind2]:
			return dp[ind1][ind2]
		if s1[ind1] == s2[ind2]:
			dp[ind1][ind2] = self.recur(ind1 - 1, ind2 - 1, s1, s2) + self.recur(ind1 - 1, ind2, s1, s2)
		else:
			dp[ind1][ind2] = self.recur(ind1 - 1, ind2, s1, s2)
		return dp[ind1][ind2]

	def countWays(self, S1, S2):
		n1 = len(S1)
		n2 = len(S2)
		dp = [[0 for j in range(n2 + 1)] for i in range(n1 + 1)]
		for i in range(n1 + 1):
			dp[i][0] = 1
		for i in range(1, n1 + 1):
			for j in range(1, n2 + 1):
				if S1[i - 1] == S2[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		return dp[n1][n2]
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def countWays(self, S1, S2):
		memo = {}

		def dfs(i, j, S1, S2):
			if j >= len(S2):
				return 1
			if i >= len(S1):
				return 0
			if (i, j) in memo:
				return memo[i, j]
			if S1[i] == S2[j]:
				memo[i, j] = dfs(i + 1, j + 1, S1, S2) + dfs(i + 1, j, S1, S2)
			else:
				memo[i, j] = dfs(i + 1, j, S1, S2)
			return memo[i, j]
		return dfs(0, 0, S1, S2)
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


from functools import lru_cache

class Solution:

	def countWays(self, s1, s2):
		(m, n) = (len(s1), len(s2))

		@lru_cache()
		def dfs(i, j):
			if j == n:
				return 1
			if i == m:
				return 0
			ans = 0
			if s1[i] == s2[j]:
				ans += dfs(i + 1, j + 1)
			ans += dfs(i + 1, j)
			return ans
		return dfs(0, 0)
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def countWays(self, S1, S2):

		def f(x, y, s1, s2, dp):
			if y <= 0:
				return 1
			if x <= 0:
				return 0
			match = 0
			not_match = 0
			if s1[x - 1] == s2[y - 1]:
				match = f(x - 1, y - 1, s1, s2, dp) + f(x - 1, y, s1, s2, dp)
			else:
				not_match = f(x - 1, y, s1, s2, dp)
			return match + not_match
		n = len(S1)
		m = len(S2)
		dp = [[]]
		return f(n, m, S1, S2, dp)
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		S1 = input()
		S2 = input()
		ob = Solution()
		ans = ob.countWays(S1, S2)
		print(ans)


class Solution:

	def f(self, i, j):
		if (i, j) in self.dp:
			return self.dp[i, j]
		if i == self.N1:
			return 1
		if j == self.N2:
			return 0
		retval = 0
		if self.s1[i] == self.s2[j]:
			retval = self.f(i + 1, j + 1)
		self.dp[i, j] = self.f(i, j + 1) + retval
		return self.dp[i, j]

	def countWays(self, s1, s2):
		self.s1 = s2
		self.s2 = s1
		self.N1 = len(s2)
		self.N2 = len(s1)
		self.dp = {}
		return self.f(0, 0)


class Solution:

	def f(self, a, b, i, j, dp):
		if i == 0 and j == 0:
			return 1
		if i > 0 and j == 0:
			return 1
		if i == 0 and j > 0:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		p = 0
		if a[i - 1] == b[j - 1]:
			p = self.f(a, b, i - 1, j - 1, dp)
		n = self.f(a, b, i - 1, j, dp)
		dp[i][j] = p + n
		return dp[i][j]

	def countWays(self, S1, S2):
		n = len(S1)
		m = len(S2)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		return self.f(S1, S2, n, m, dp)


class Solution:

	def countWays_rec(self, s1, s2, len_s1, len_s2, itr_s1, itr_s2, ways):
		if itr_s2 == len_s2 and itr_s1 == len_s1 or itr_s2 == len_s2:
			ways[0] = ways[0] + 1
			return
		if itr_s1 == len_s1:
			return
		if s1[itr_s1] == s2[itr_s2]:
			self.countWays_rec(s1, s2, len_s1, len_s2, itr_s1 + 1, itr_s2 + 1, ways)
			self.countWays_rec(s1, s2, len_s1, len_s2, itr_s1 + 1, itr_s2, ways)
		else:
			self.countWays_rec(s1, s2, len_s1, len_s2, itr_s1 + 1, itr_s2, ways)

	def countWays_dp(self, s1, s2):
		ways = 1
		len_s1 = len(s1)
		len_s2 = len(s2)
		dp = [[0 for _ in range(len_s1 + 1)] for __ in range(len_s2 + 1)]
		for _ in range(len_s2):
			dp[_][0] = 0
		for _ in range(len_s1):
			dp[0][_] = 1
		for i in range(1, len_s2 + 1):
			for j in range(1, len_s1 + 1):
				if s1[j - 1] == s2[i - 1]:
					dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
				else:
					dp[i][j] = dp[i][j - 1]
		return dp[-1][-1]

	def countWays(self, S1, S2):
		return self.countWays_dp(S1, S2)