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(nm).
Expected Auxiliary Space: O(nm).
Constraints:
1 ≤ length of(T) ≤ 100
1 ≤ length of(S) ≤ 8000

见题面

见题面