AT_abc214_f [ABC214F] Substrings

题目描述

给定一个字符串 $S$。高桥君按照以下步骤从该字符串构造一个新字符串 $T$。

• 首先，在 $S$ 的一个或多个字符上做标记。但被标记的字符不能相邻。
• 接着，删除所有未被标记的字符。
• 最后，将剩下的字符按原顺序组成字符串 $T$。注意，不能改变字符的顺序。

请问，作为 $T$ 可能出现的不同字符串有多少种？请输出对 $10^9+7$ 取模的结果。

输入格式

输入为以下格式，从标准输入读取。

$S$

输出格式

输出作为 $T$ 可能出现的不同字符串的种数，对 $10^9+7$ 取模。

样例 1

输入

abc

输出

4

样例 2

输入

aa

输出

1

样例 3

输入

acba

输出

6

样例 4

输入

chokudai

输出

54

说明/提示

限制条件

• $S$ 仅由小写英文字母组成，长度为 $1$ 到 $2 \times 10^5$。

样例解释 1

作为 $T$ 可能出现的字符串有 a、b、c、ac 共 $4$ 种。当只标记 $S$ 的第 $1$ 个字符时，$T$ 为 a；只标记第 $2$ 个字符时，$T$ 为 b；只标记第 $3$ 个字符时，$T$ 为 c；标记第 $1$ 个和第 $3$ 个字符时，$T$ 为 ac。注意，不能同时标记第 $1$ 个和第 $2$ 个字符。

样例解释 2

作为 $T$ 可能出现的字符串只有 a。注意，即使标记的位置不同，也可能得到相同的 $T$。

样例解释 3

作为 $T$ 可能出现的字符串有 a、b、c、aa、ab、ca 共 $6$ 种。

由 ChatGPT 4.1 翻译