Substrings

题目描述

给定一个字符串 $S$。Takahashi 将从这个字符串构造一个新字符串 $T$，方法如下。

首先，在 $S$ 中标记一个或多个字符。这里，任意两个被标记的字符不得相邻。
接着，删除所有未被标记的字符。
最后，令 $T$ 为剩下的字符串。这里禁止改变字符的顺序。

有多少种字符串可以作为 $T$ 得到？求计数对 $(10^9 + 7)$ 取模后的值。

输入格式

从标准输入给出，格式如下： $S$

输出格式

输出可以作为 $T$ 得到的不同字符串的数量，对 $(10^9 + 7)$ 取模。

abc

4

aa

1

acba

6

chokudai

54

提示

$S$ 是一个长度在 $1$ 到 $2 \times 10^5$（含）之间的字符串，由小写英文字母组成。可以得到的 $T$ 有四个字符串：$a$、$b$、$c$ 和 $ac$。
标记 $S$ 的第一个字符得到 $a$；
标记 $S$ 的第二个字符得到 $b$；
标记 $S$ 的第三个字符得到 $c$；
标记第一个和第三个字符得到 $ac$。
注意，例如标记第一和第二个字符是被禁止的。
只有一个字符串可以得到 $T$，即 $a$。
注意标记不同的位置可能得到相同的字符串。
可以得到的 $T$ 有六个字符串：$a$、$b$、$c$、$aa$、$ab$、和 $ca$。

标签: AtCoder|abc214F

来源

AtCoder|abc214F