子序列

题目描述

给定一个字符串 $S$。高桥君要按以下方式用 $S$ 造出一个新的字符串 $T$。

首先,在 $S$ 中标记一个或多个字符。这里,任意两个被标记的字符不能相邻。

接下来,删除所有未被标记的字符。

最后,令 $T$ 为剩下的字符串。这里,不允许改变字符的顺序。

有多少种不同的字符串可以作为 $T$ 得到？求个数对 $(10^9 + 7)$ 取模后的值。

输入格式

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

$S$

输出格式

输出可以作为 $T$ 得到的不同字符串的个数,对 $(10^9 + 7)$ 取模。

样例

abc

4

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

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

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

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

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

注意,例如同时标记第一个和第二个字符是不允许的。

aa

1

可以作为 $T$ 得到的字符串只有 1 个,即 a。

注意,标记不同的位置可能得到相同的字符串。

acba

6

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

chokudai

54

数据范围

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