F - 子字符串

得分：$500$ 分

问题描述

给定一个字符串 $S$。高哈什会按照以下方式将其转换成一个新的字符串 $T$。

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

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

约束

• $S$ 是一个长度在 $1$ 到 $2 \times 10^5$（包括端点）之间的字符串，由小写英文字母组成。

输入

输入以以下格式从标准输入中给出：

$S$

输出

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

abc

4

有四个字符串可以作为 $T$ 得到：a、b、c 和 ac。

将 $S$ 的第一个字符标记为 a；

将 $S$ 的第二个字符标记为 b；

将 $S$ 的第三个字符标记为 c；

将 $S$ 的第一个和第三个字符标记为 ac。

请注意，禁止标记第一个和第二个字符的两个位置。

aa

1

只有一个字符串可以作为 $T$ 得到，那就是 a。 注意，标记不同的位置可能会得到相同的字符串。

acba

6

有六个字符串可以作为 $T$ 得到：a、b、c、aa、ab 和 ca。

chokudai

54