Distinct subsequence count

Write codeHard25 min

Your task

Given strings s and t, count the number of distinct subsequences of s that equal t. A subsequence keeps relative order but may drop characters. The count fits in a 64-bit integer. Either string may be empty; the empty string is a subsequence of any string exactly once.

Examples

distinct_subseq(s: str, t: str) -> int
Example 1
Inputdistinct_subseq("rabbbit", "rabbit")
Output3