Score : $500$ points

问题描述

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

• 首先，在字符串 $S$ 中标记一个或多个字符。注意，相邻的两个字符不能都被标记。
• 然后，删除所有未被标记的字符。
• 最后，将剩余的字符串定义为 $T$。在此过程中，禁止改变字符的顺序。

有多少种可能得到的字符串 $T$？请计算这些字符串的数量对 $(10^9 + 7)$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:31:55