P7888 "MCOI-06" Distinct Subsequences

You are given a string $S$ consisting of lowercase letters. Define the value of a string as the number of **distinct** non-empty subsequences of this string, where a subsequence is allowed to be the whole string itself. Find the sum of the values of **all** subsequences of $S$. Output the answer modulo $10^9+7$.

The first line contains a string $S$ consisting of lowercase letters.

Output one line containing the answer.

#### Constraints **This problem uses bundled testdata.** - Subtask 1 (5 pts): $|S|\le 11$. - Subtask 2 (10 pts): $|S|\le 22$. - Subtask 3 (20 pts): $|S|\le 100$ and $S$ consists only of `a` and `b`. - Subtask 4 (30 pts): $|S|\le 5000$. - Subtask 5 (35 pts): no special restrictions. For $100\%$ of the testdata, $1\le |S|\le 10^6$, and $S$ is guaranteed to consist only of lowercase letters. Translated by ChatGPT 5