Number of Distinct Common Subsequences

Problem Statement

Number of Distinct Common Subsequences You are given two strings, s of length n and t of length m , both consisting of lowercase Latin letters. A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly zero or all) characters. Let’s call a string k a common subsequence of both strings s and t if k is a subsequence of both s and t . Find the number of distinct strings k that are common subsequences of both s and t . Since the answer can be very large, print it modulo 10 9 + 7 . Input Format The first line contains an integer n , denoting the length of string s . The next line contains an integer m , denoting the length of string t . The next line contains a string s , denoting the given string. The next line contains a string t , denoting the given string. Output Format Print the number of distinct strings k that are common subsequences of both s and t , modulo 10 9 + 7 . Constraints 1 ≤ n ≤ 1000 1 ≤ m ≤ 1000 1 ≤ len(s) ≤ 1000 1 ≤ len(t) ≤ 10