AT_abc214_f [ABC214F] Substrings

[problemUrl]: https://atcoder.jp/contests/abc214/tasks/abc214_f 文字列 $ S $ が与えられます。高橋君はこの文字列から以下の手順にしたがって新しい文字列 $ T $ を作ります。 - まず、$ S $ の文字のうちの一つ以上に印をつける。ただし、印をつけた文字どうしが隣り合ってはならない。 - 次に、印がついていない文字を全て削除する。 - 最後に、残った文字列を $ T $ とする。ただし、この時に文字を並び替えてはならない。 $ T $ としてありうる文字列は何種類ありますか？ $ (10^9\ +\ 7) $ で割ったあまりを求めてください。

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

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

### 制約 - $ 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 $ つです。