配点 : $500$ 点

問題文

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

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

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

制約

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

入力

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

$S$

出力

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

abc

4

$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$ 文字目の両方に印をつけることはできないことに注意してください。

aa

1

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

acba

6

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

chokudai

54