# Distinct Subsequences
## Problem Statement
Given a string $S$ of length $n$, your task is to find the total number of distinct subsequences of $S$, modulo $10^9 + 7$.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, if $S = \text{"abc"}$, its distinct subsequences are $\text{""}$, $\text{"a"}$, $\text{"b"}$, $\text{"c"}$, $\text{"ab"}$, $\text{"ac"}$, $\text{"bc"}$, $\text{"abc"}$.
## Input Format
- First line: an integer $n$ ($1 \le n \le 10^5$) - The length of the string $S$.
- Second line: a string $S$ - A string of $n$ lowercase English letters.
## Output Format
A single integer, representing the number of distinct subsequences of $S$, modulo $10^9 + 7$.
## Sample Test Cases
### Sample Input 1
```
3
abc
```
### Sample Output 1
```
8
```
### Sample Input 2
```
3
aba
```
### Sample Output 2
```
7
```
### Sample Input 3
```
5
abab
```
### Sample Output 3
```
12
```
## Constraints
- $1 \le n \le 10^5$
- The string $S$ consists only of lowercase English letters (`'a'` through `'z'`).
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
**Sample 1: $S = \text{"abc"}$**
The distinct subsequences are:
- Empty string: $\text{""}$
- Length 1: $\text{"a"}$, $\text{"b"}$, $\text{"c"}$
- Length 2: $\text{"ab"}$, $\text{"ac"}$, $\text{"bc"}$
- Length 3: $\text{"abc"}$
Total: $1+3+3+1 = 8$.
**Sample 2: $S = \text{"aba"}$**
The distinct subsequences are:
- Empty string: $\text{""}$
- Length 1: $\text{"a"}$, $\text{"b"}$
- Length 2: $\text{"aa"}$ (from $S_0, S_2$), $\text{"ab"}$ (from $S_0, S_1$), $\text{"ba"}$ (from $S_1, S_2$)
- Length 3: $\text{"aba"}$ (from $S_0, S_1, S_2$)
Total: $1+2+3+1 = 7$. Note that $\text{"a"}$ can be formed in two ways ($S_0$ or $S_2$), but it's counted only once as a distinct subsequence. Similarly for $\text{"ab"}$ (e.g., $S_0S_1$ or $S_0S_2$ if $S_2$ were 'b'), but here it is only formed by $S_0S_1$.
Loading problem statement...