Problem Description

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$.

Input Format

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

Output Format

Output one line containing the answer.

ab

5

sapnap

593

abcbdabcbabcd

938773

tobeornottobethatisthequestion

769276982

Hint

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