問題文

英小文字からなる文字列 $S$ が与えられます．

$S$ の長さを $N$ とすると，$S$ の非空な部分列は全部で $2^N-1$ 個あります（$2$ つの部分列が文字列として同じでも，取り出す位置が異なれば区別します）．

$2^N-1$ 個の各部分列について連 (Run) の個数を求め，その総和を ${10}^9+7$ で割った余りを求めてください．

ここで，文字列の連とは，「同一の文字が連続する非空かつ極大な区間」を指します． 例えば，abbbacc の連は a，bbb，a，cc の $4$ つです． $2$ つの連が文字列として同じでも，位置が異なれば区別することに注意してください．

入力

入力は以下の形式で与えられる:

$S$

• $S$ は英小文字のみからなる文字列
• $1\le |S|\le 2\times {10}^5$

出力

連の個数の総和を ${10}^9+7$ で割った余りを出力せよ． 最後に改行を出力すること．

サンプル

aba

11

zzzzzzz

127

abcaaabacc

3856

supercalifragilisticexpialidocious

636565047