题目描述

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

• 首先，给 $S$ 中至少一个字符做标记。但标记的字符不能相邻。
• 其次，删除所有未标记的字符。
• 最后，将剩余字符作为 $T$。此时不能改变字符的顺序。

问有多少种可能的 $T$？结果对 $(10^9 + 7)$ 取模。

输入格式

输入通过标准输入按以下形式给出。

$S$

输出格式

输出可能的 $T$ 的种类数对 $(10^9 + 7)$ 取模的结果。

输入输出样例 #1

输入 #1

abc

输出 #1

4

输入输出样例 #2

输入 #2

aa

输出 #2

1

输入输出样例 #3

输入 #3

acba

输出 #3

6

输入输出样例 #4

输入 #4

chokudai

输出 #4

54

说明/提示

约束条件

• $S$ 仅由小写英文字母组成，长度为 1 以上 $2×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 种。