题目描述

文字列 $S$ が与えられます。高橋君はこの文字列から以下の手順にしたがって新しい文字列 $T$ を作ります。

• まず、$S$ の文字のうちの一つ以上に印をつける。ただし、印をつけた文字どうしが隣り合ってはならない。
• 次に、印がついていない文字を全て削除する。
• 最後に、残った文字列を $T$ とする。ただし、この時に文字を並び替えてはならない。

$T$ としてありうる文字列は何種類ありますか？ $(10^9\ +\ 7)$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

$T$ としてありうる文字列の種類数を $(10^9\ +\ 7)$ で割ったあまりを出力せよ。

题目大意

给出字符串 $S(1\le|S|\le2\times10^5)$，你可以通过如下操作得到字符串 $T$。

• 首先，标记 $S$ 中若干个不相邻的字符。
• 接下来，删除所有未被标记的字符。
• 最后，将剩余的字符拼接起来得到 $T$。

问有多少种本质不同的 $T$。答案对 $10^9+7$ 取模。

abc

4

aa

1

acba

6

chokudai

54

提示

制約

• $S$ は英小文字のみからなる長さ $1$ 以上 $2\ \times\ 10^5$ 以下の文字列

Sample Explanation 1

$T$ としてありうるものは a、 b、 c、 ac の $4$ つです。 $S$ の $1$ 文字目のみに印をつけたとき $T$ は a、 $S$ の $2$ 文字目のみに印をつけたとき $T$ は b、 $S$ の $3$ 文字目のみに印をつけたとき $T$ は c、 $S$ の $1$ 文字目と $3$ 文字目のみに印をつけたとき $T$ は ac、 となります。例えば $1$ 文字目と $2$ 文字目の両方に印をつけることはできないことに注意してください。

Sample Explanation 2

$T$ としてありうるものは a のみです。 印をつけた位置が異なっていても $T$ が同じ文字列となる可能性があることに注意してください。

Sample Explanation 3

$T$ としてありうるものは a、 b、 c、 aa、 ab、 ca の $6$ つです。