題干：

The Fair Nut found a string?ss. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences?p1,p2,…,pkp1,p2,…,pk, such that:

For each?ii?(1≤i≤k1≤i≤k),?spi=spi=?'a'.

For each?ii?(1≤i<k1≤i<k), there is such?jj?that?pi<j<pi+1pi<j<pi+1?and?sj=sj=?'b'.

The Nut is upset because he doesn't know how to find the number. Help him.

This number should be calculated modulo?109+7109+7.

Input

The first line contains the string?ss?(1≤|s|≤1051≤|s|≤105) consisting of lowercase Latin letters.

Output

In a single line print the answer to the problem?— the number of such sequences?p1,p2,…,pkp1,p2,…,pk?modulo?109+7109+7.

Examples

Input

abbaa

Output

5

Input

baaaa

Output

4

Input

agaa

Output

3

Note

In the first example, there are?55?possible sequences.?[1][1],?[4][4],?[5][5],?[1,4][1,4],?[1,5][1,5].

In the second example, there are?44?possible sequences.?[2][2],?[3][3],?[4][4],?[5][5].

In the third example, there are?33?possible sequences.?[1][1],?[3][3],?[4][4].

題目大意：

? ?讓你構造一個序列，有兩個要求：1.全為‘a’字符。2.每兩個a字符之間一定夾著至少一個b字符，求能構造出多少個這樣的序列

解題報告：

? ?掃一遍遇到a就記錄，遇到b就終止并開始計數 最后輸出答案，就行了

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; char s[MAX]; int main() {scanf("%s", s + 1);int len = strlen(s + 1);ll ans = 1;for(int i = 1; i<=len; i++){ll cnt = 0;int cur = i;while(cur <= len){if(s[cur] == 'a') cnt++,cur++;else if(s[cur] == 'b') break;else cur++;}i = cur;ans = ans*(cnt+1) % mod;}ans--;printf("%lld\n", ans);return 0;}

?

總結

以上是生活随笔為你收集整理的【CodeForces - 1084C】The Fair Nut and String（思维，组合数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。