102145: [AtCoder]ABC214 F - Substrings

Problem Statement

Given is a string $S$. From this string, Takahashi will make a new string $T$ as follows.

• First, mark one or more characters in $S$. Here, no two marked characters should be adjacent.
• Next, delete all unmarked characters.
• Finally, let $T$ be the remaining string. Here, it is forbidden to change the order of the characters.

How many strings are there that can be obtained as $T$? Find the count modulo $(10^9 + 7)$.

Constraints

• $S$ is a string of length between $1$ and $2 \times 10^5$ (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the number of different strings that can be obtained as $T$, modulo $(10^9 + 7)$.

Sample Input 1

abc

Sample Output 1

4

There are four strings that can be obtained as $T$: a, b, c, and ac.

Marking the first character of $S$ yields a;

marking the second character of $S$ yields b;

marking the third character of $S$ yields c;

marking the first and third characters of $S$ yields ac.

Note that it is forbidden to, for example, mark both the first and second characters.

Sample Input 2

aa

Sample Output 2

1

There is just one string that can be obtained as $T$, which is a. Note that marking different positions may result in the same string.

Sample Input 3

acba

Sample Output 3

6

There are six strings that can be obtained as $T$: a, b, c, aa, ab, and ca.

Sample Input 4

chokudai

Sample Output 4

54

问题描述

给定一个字符串$S$。高桥同学将按照以下方式从这个字符串中创建一个新的字符串$T$。

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

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

约束

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

输入

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

$S$

输出

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

样例输入 1

abc

样例输出 1

4

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

标记$S$的第一个字符得到a；

标记$S$的第二个字符得到b；

标记$S$的第三个字符得到c；

标记$S$的第一个和第三个字符得到ac。

注意，例如，禁止标记第一个和第二个字符。

样例输入 2

aa

样例输出 2

1

可以作为$T$获得的字符串只有一个，即a。 注意，标记不同的位置可能会导致相同的字符串。

样例输入 3

acba

样例输出 3

6

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

样例输入 4

chokudai

样例输出 4

54