Distinct Subsequences

Problem

Given a string s and a string t, count the number of distinct subsequences of t in s. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example

Given s = "rabbbit", t = "rabbit", return 3.