/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
文字列 S が与えられます。高橋君はこの文字列から以下の手順にしたがって新しい文字列 T を作ります。
- まず、S の文字のうちの一つ以上に印をつける。ただし、印をつけた文字どうしが隣り合ってはならない。
- 次に、印がついていない文字を全て削除する。
- 最後に、残った文字列を T とする。ただし、この時に文字を並び替えてはならない。
T としてありうる文字列は何種類ありますか？ (10^9 + 7) で割ったあまりを求めてください。
制約
- S は英小文字のみからなる長さ 1 以上 2 \times 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
T としてありうる文字列の種類数を (10^9 + 7) で割ったあまりを出力せよ。
入力例 1
abc
出力例 1
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 文字目の両方に印をつけることはできないことに注意してください。
入力例 2
aa
出力例 2
1
T としてありうるものは a のみです。
印をつけた位置が異なっていても T が同じ文字列となる可能性があることに注意してください。
入力例 3
acba
出力例 3
6
T としてありうるものは a、 b、 c、 aa、 ab、 ca の 6 つです。
入力例 4
chokudai
出力例 4
54
Score : 500 points
Problem Statement
Given is a string S. From this string, Takahashi will make a new string T as follows.
- First, mark one or more characters in S. Here, no two marked characters should be adjacent.
- Next, delete all unmarked characters.
- Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.
How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).
Constraints
- S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of different strings that can be obtained as T, modulo (10^9 + 7).
Sample Input 1
abc
Sample Output 1
4
There are four strings that can be obtained as T: a, b, c, and ac.
Marking the first character of S yields a;
marking the second character of S yields b;
marking the third character of S yields c;
marking the first and third characters of S yields ac.
Note that it is forbidden to, for example, mark both the first and second characters.
Sample Input 2
aa
Sample Output 2
1
There is just one string that can be obtained as T, which is a.
Note that marking different positions may result in the same string.
Sample Input 3
acba
Sample Output 3
6
There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.
Sample Input 4
chokudai
Sample Output 4
54