Count the Number of Distinct Subsequences

In the Royal Cipher Office of Prime City, the Cryptographer must count the number of distinct subsequences of a given string. A subsequence is any sequence derived by deleting zero or more characters without changing the order of the remaining characters. "Use dynamic programming," the Cryptographer says. "Let dp[i] be the number of distinct subsequences of the first i characters. dp[i] = 2 * dp[i-1] - dp[lastSeen[char] - 1] if the character was seen before, else 2 * dp[i-1]. The empty subsequence counts as one." Given a string S, count the number of distinct subsequences (including the empty one) modulo 10^9 + 7. Constraints: 1 <= |S| <= 10^5, S contains lowercase English letters Input: abc Output: 8 Input: aaa Output: 4