You are given two strings, s and t.
A subsequence of s is what you get when you delete some letters (maybe none) and keep the rest in the same order. Two subsequences are counted as different when they use different positions of s, even if the letters look the same.
Count how many different subsequences of s are equal to t and return that count. The tests are made so that the answer fits in a 32-bit signed integer.
Examples
Example 1:
Input: s = "abab", t = "ab"
Output: 3
Explanation: Use positions (0,1), (0,3) or (2,3). That is 3 ways.
Example 2:
Input: s = "aaaa", t = "aa"
Output: 6
Explanation: Pick any 2 of the 4 letters "a". That is 6 ways.
Example 3:
Input: s = "abc", t = "d"
Output: 0
Explanation: There is no "d" in s, so there is no way.