The Fair Nut found a string $s$. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences $p_1, p_2, \ldots, p_k$, such that:   For each $i$ ($1 \leq i \leq k$), $s_{p_i} =$ 'a'.  For each $i$ ($1 \leq i < k$), there is such $j$ that $p_i < j < p_{i + 1}$ and $s_j =$ 'b'. 

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

This number should be calculated modulo $10^9 + 7$.


-----Input-----

The first line contains the string $s$ ($1 \leq |s| \leq 10^5$) consisting of lowercase Latin letters.


-----Output-----

In a single line print the answer to the problem — the number of such sequences $p_1, p_2, \ldots, p_k$ modulo $10^9 + 7$.


-----Examples-----
Input
abbaa

Output
5
Input
baaaa

Output
4
Input
agaa

Output
3


-----Note-----

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

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

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

Difficulty: interview

Starter code:

Solutions:
s=input()
n=len(s)
a=[]
curr=0
for i in range(n):
    if s[i]=="a":
        curr+=1
    elif s[i]=="b":
        a.append(curr)
        curr=0
if curr>0:
    a.append(curr)
prod=1
for i in range(len(a)):
    prod*=(a[i]+1)
    prod=prod%1000000007
print(prod-1)

s = input()
lengths = []
cnt = 0
eps = 1e-8

for c in s:
    if c == 'b':
        if cnt > 0: lengths.append(cnt)
        cnt = 0
    elif c == 'a':
        cnt += 1
if cnt > 0:
    lengths.append(cnt)
    cnt = 0


ans = 1
for l in lengths:
    ans *= (l + 1)
    ans %= (1e9 + 7)
ans -= 1
print(int(ans % (1e9 + 7) + eps))

s = input()
t = ''
for i in range(len(s)):
    if s[i] == 'a' or s[i] == 'b':
        t += s[i]
boo = False
t += 'b'
ans = 1
cur = 0
for i in range(len(t)):
    if boo:
        if t[i]=='a':
            cur += 1
        else:
            ans *= cur
            ans %= 1000000007
            boo = False
    else:
        if t[i]=='a':
            cur = 2
            boo = True
print((ans-1)%1000000007)


s = input()
p = 10**9 + 7
a = []
#ind = []
#k = -1
for ch in s:
    if ch == 'a':
        if len(a)==0 or a[-1][1] == True:
            a += [(1,False)]
        else:
            a[-1] = (a[-1][0]+1,False)
    if ch == 'b' and len(a) > 0:
        a[-1] = (a[-1][0],True)
n = len(a)
dp = {}
dp[n] = 1
for i in range(n-1, -1, -1):
    dp[i] = (dp[i+1] * (1+a[i][0]))%p
print((dp[0]-1)%p)


import sys


s = input()

t = ''

for i in s:
    if(i == 'a' or i == 'b'):
        t+=i


posj = []
for i in range(len(t)):
    if(t[i] == 'b'):
        posj.append(i)
if(len(posj) == 0):
    print(len(t))
    return


mids = [posj[0] + 1]

mod = 10**9 + 7
sub1 = 0
for i in range(len(posj)-1):
    mid = posj[i + 1] - posj[i]
    
    mids.append(mid)
mids.append(len(t) - posj[-1])

tot = 1

for i in mids:
    tot *= i
    tot %= mod
tot -= 1
print(tot%mod)





s1 = input()
s = ""
for i in s1:
    if (i in "ab"):
        s += i
n = len(s)
ans = 1
i = 0
while (i < n):
    x = 0
    while(i < n and s[i] == "a"):
        i += 1
        x += 1
    ans *= (x + 1)
    i += 1
MOD = 10 ** 9 + 7
print((ans - 1) % MOD)

def prog():
    s = input()
    ab = []
    mod = (10**9)+7
    ans = 1
    cnt = 1
    for i in s:
        if(i=='a'):
            cnt+=1
        elif(i=='b'):
            ans = (ans*cnt)%mod
            cnt = 1
    ans = (ans*cnt)%mod
    ans-=1
    while(ans<0):
        ans+=mod
    return (ans%mod)
print(prog())

s = input()
withb = 0
withoutb = 0
ans = 0
for i in s:
    if i == "a":
        ans += withb + 1
        ans %= 10 ** 9 + 7
        withoutb += withb + 1
        withoutb %= 10 ** 9 + 7
    elif i == "b":
        withb += withoutb
        withb %= 10 ** 9 + 7
        withoutb = 0
print(ans % (10 ** 9 + 7))
    


n=input()
k=[]
i=0
a=len(n)
x=0
p=1
q=0
while i<a:
    if n[i]=='a':
        q+=1
        x+=1
    if n[i]=='b':
        p=0
        k+=[x]
        x=0
    i+=1
k+=[x]
if p==1:
    print (q)
else:
    z=1
    for i in k:
       z*=(i+1)
    z-=1
    print (z%(10**9+7))

s = input()
L = []
temp = 0
for i in range(0,len(s)):
    if s[i] == 'a':
        temp += 1
    elif s[i] == 'b':
        if temp > 0:
            L.append(temp)
            temp = 0
if temp > 0:
    L.append(temp)

ans = 1
for i in L:
    ans = (ans*(i+1))%(1000000007)

print((ans-1)%(1000000007))


s = input()

l = []

c = 0

for i in s:
    if i == 'a':
        c += 1
    elif i == 'b':
        if c:
            l.append(c)
            c = 0

if c:
    l.append(c)

md = 10**9 + 7

ans = 0

#print(l)

d = {}

def inverse(a, n):
    if a in d:
        return d[a]
    t = 0
    t1 = 1
    r = n
    r1 = a
    while r1 > 0:
        q = r // r1
        tmp = t- q*t1
        t = t1
        t1 = tmp

        tmp = r - q*r1
        r = r1
        r1 = tmp

    if t < 0:
        t += n
    t = (t+n) % n
    d[a] = t
    return t


mul = 1
for i in l:
    mul *= i+1
    mul %= md

for i in range(len(l)):
    mul = (mul * inverse(l[i]+1, md) ) % md
    m = mul * l[i]
    m %= md

    ans += m
    ans %= md

print(ans)


    



m = 10**9+7

s = input()

r = x = 1
for c in s:
    if c == 'b':
        r = (r * x) % m
        x = 1
    elif c == 'a':
        x += 1
r = (r * x) % m

print(r - 1)


s = input();
mod = 1e9 + 7

ans = 1;
cnt = 0
for i in range(len(s)):
	if s[i] != 'b':
		if s[i]=='a':
			cnt += 1
	else:
		if cnt>0:
			ans = (ans*(cnt+1))%mod
		cnt = 0

if cnt>0:
	ans = (ans*(cnt+1))%mod
	
print(int(ans)-1)


s=input()
m=10**9+7
l=list()
count=0
for c in s:
    if c=='a':
        count+=1
    if c=='b' and count>0:
        l.append(count)
        count=0
if count>0:
    l.append(count)
ans=1
for i in l:
    ans=(ans*(i+1))%m
print(ans-1)

inp_s = input()
mod = 10 ** 9 + 7
i = 0
l = len(inp_s)
r = 0
while i < l:
    a = 0
    while i < l and inp_s[i] != 'b':
        if inp_s[i] == 'a':
            a += 1
        i += 1
    r = (r + r * a + a) % mod
    i += 1

print(r)


mod=1000000007
s=str(input())
ans=1
count1=0
arr=[]
i=0
while(i<len(s)):
    if(s[i]=='b'):
        i+=1
        break
    elif(s[i]=='a'):
        i+=1
        count1+=1
    else:
        i+=1
count2=0
while(i<len(s)):
    if(s[i]=='b'):
        if(count2>0):
            arr.append(count1)
            count1=count2
            count2=0
    elif(s[i]=='a'):
        count2+=1
    i+=1
if(count1>0):
    arr.append(count1)
if(count2>0):
    arr.append(count2)
for i in range(len(arr)):
    ans=((ans%mod)*((arr[i]%mod+1%mod)%mod))%mod
#print(ans,arr)
ans=((ans%mod-1%mod)%mod+mod)%mod
print(ans)

check=input()
ans=0
back=0
for i in range (len(check)-1,-1,-1):
    if check[i:i+1]=='a':
        ans+=((1+back)%(10**9+7))
    elif check[i:i+1]=='b':
        back=ans
print(ans%(10**9+7))

S=input()
mod=10**9+7

ANS=0
YET=0
OK=0

for s in S:
    if s=="a":
        YET+=(OK+1)%mod
        ANS=(ANS+OK+1)%mod

    elif s=="b":
        OK=(OK+YET)%mod
        YET=0

    #print(YET,OK,ANS)

print(ANS)


mod = int(1e9) + 7

s = input()
n = len(s)

ans = 1
kol = 0
tmp = 0
for c in s:
	if c == 'b':
		ans *= (kol + 1)
		ans = ans % mod
		kol = 0
	if c == 'a':
		kol += 1
		tmp += 1
print((ans * (kol + 1) - 1) % mod)



#!/usr/bin/env python
# coding: utf-8

# In[38]:


string=list(input())


# In[39]:


n=len(string)


# In[11]:





# In[40]:


asubsets=[]
a=0
b=1
for i in range(n):

        if string[i]=="a":
            a=a+1
            
            
        if string[i]=="b":
            asubsets.append(a)
            a=0
            
asubsets.append(a)    
#print(asubsets)


# In[41]:


increase=[i+1 for i in asubsets]


# In[42]:


total=1

for i in increase:
    total=total*i
    


# In[43]:


finaltotal=(total-1)%(pow(10,9)+7)


# In[44]:


print(finaltotal)


# In[ ]:


s = input()
m = 10**9+7
a = []
j = 0
for i in range(len(s)):
    if s[i] == 'b':
        a.append(j)
        j = 0
    elif s[i] == 'a':
        j += 1
if j != 0:
    a.append(j)
if len(a) == 0:
    print(0)
    return

ans = a[0]
for i in range(1, len(a)):
    ans = (ans+ans*a[i]+a[i])%m
print(ans)

s=input()
n=len(s)
b=[]
a=[0]*n
MOD=10**9+7
if s[0]=='a':
	a[0]=1
if s[0]=='b':
	b.append(0)
for i in range(1,n):
	a[i]=a[i-1]
	if s[i]=='a':
		a[i]+=1
		if len(b)>0:
			p=b[-1]
			if p>0:
				a[i]+=a[p-1]
	elif s[i]=='b':
		b.append(i)
	a[i]%=MOD
print(a[n-1]%MOD)
		


def p(arr, n): 
    ans = 1; 
    for i in range(0,n): 
        ans = ans * (arr[i] + 1) 
    return ans-1
s=input()
a=[]
k=0
for i in s:
    if i=='a':
        k+=1
    elif i=='b':
        if k!=0:
            a.append(k)
        k=0
if k!=0:
    a.append(k)
print(p(a,len(a))%1000000007)

import sys, math
s=[x for x in input()]
string=[]
last=''
for i in range(len(s)):
  if s[i]=='a' or s[i]=='b':
    if last!=s[i]:
      last=s[i]
      string.append([s[i], 0])
    string[-1][-1]+=1
res=[0]
summa=0
for i in range(len(string)):
  if string[i][0]=='a':
    res.append(string[i][1])
    res[-1]+=string[i][1]*res[-2]
    res[-1]+=res[-2]
    summa+=res[-1]
if len(res)==0:
  print (0)
else:
  print (res[-1]%(1000000000+7))