No.1171 Runs in Subsequences
opt
Kiri8128Problem Statement
You are given a string $S$ consisting of lowercase English letters.
Let $N$ be the length of $S$. Then $S$ has a total of $2^N-1$ non-empty subsequences (even if $2$ subsequences are the same as strings, they are distinguished if the positions they are taken from differ).
For each of the $2^N-1$ subsequences, find the number of runs (Run), and compute the sum of these numbers modulo $10^9 + 7$.
Here, a run of a string is a non-empty maximal segment of consecutive identical characters.
For example, the runs of abbbacc are the $4$ runs a, bbb, a, and cc.
Note that even if $2$ runs are the same as strings, they are distinguished if their positions differ.
Input
The input is given in the following format:
$S$
- $S$ is a string consisting only of lowercase English letters
- $1 \leq |S| \leq 2 \times 10^5$
Output
Output the sum of the numbers of runs modulo $10^9 + 7$. Print a newline at the end.
Sample
Sample 1
Input
aba
Output
11
The non-empty subsequences of aba are the $7$ subsequences a, b, a, ab, aa, ba, and aba.
The sum of their numbers of runs is $1+1+1+2+1+2+3 = 11$.
Sample 2
Input
zzzzzzz
Output
127
There are $2^7-1 = 127$ non-empty subsequences. Each of them has exactly $1$ run, so output $127$.
Sample 3
Input
abcaaabacc
Output
3856
Sample 4
Input
supercalifragilisticexpialidocious
Output
636565047
Output the remainder when divided by $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。