Distinct Subsequences

Hard

Given two strings s and t, return the number of distinct subsequences of s that equal t. The answer fits in a 32-bit integer.

Example 1

Input:  s = "rabbbit", t = "rabbit"
Output: 3

Example 2

Input:  s = "babgbag", t = "bag"
Output: 5

Constraints

• 1 <= s.length, t.length <= 1000
• Inputs consist of English letters.