Given a string S, the task is to count number of subsequences of the form a^{i}b^{j}c^{k}, where i >= 1, j >=1 and k >= 1.
Note: 
1. Two subsequences are considered different if the set of array indexes picked for the 2 subsequences are different.
2.  For large test cases, the output value will be too large, return the answer MODULO 10^9+7
 
Example 1:
Input:
S = "abbc"
Output: 3
Explanation: Subsequences are abc, abc and abbc.
Example 2:
Input:
S = "abcabc"
Output: 7
Explanation: Subsequences are abc, abc,
abbc, aabc abcc, abc and abc.
Your Task:
You don't need to read input or print anything. Your task is to complete the function fun() which takes the string S as input parameter and returns the number of subsequences which follows given condition.
Expected Time Complexity: O(Length of String).
Expected Auxiliary Space: O(1) .
Constraints:
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def fun(self,s):

        # code here

Solutions:
class Solution:

	def fun(self, s):
		arr = list(s)
		a = ab = abc = 0
		for i in range(len(arr)):
			if arr[i] == 'a':
				a = 2 * a + 1
			elif arr[i] == 'b':
				ab = 2 * ab + a
			elif arr[i] == 'c':
				abc = 2 * abc + ab
		return abc % 1000000007


class Solution:

	def fun(self, S: str) -> int:
		MOD = int(1000000000.0) + 7
		(aCount, bCount, cCount) = (0, 0, 0)
		for ch in S:
			if ch == 'a':
				aCount = 2 * aCount + 1
			elif ch == 'b':
				bCount = 2 * bCount + aCount
			elif ch == 'c':
				cCount = 2 * cCount + bCount
		return cCount % MOD


class Solution:

	def fun(self, s):
		n = len(s)
		a_count = 0
		ab_count = 0
		abc_count = 0
		for i in range(n):
			if s[i] == 'a':
				a_count = 2 * a_count + 1
			elif s[i] == 'b':
				ab_count = 2 * ab_count + a_count
			elif s[i] == 'c':
				abc_count = 2 * abc_count + ab_count
		return abc_count % (10 ** 9 + 7)


class Solution:

	def fun(self, s):
		(ac, abc, abcc, mod) = (0, 0, 0, 1000000007)
		for i in s:
			if i == 'a':
				ac += ac + 1
				ac %= mod
			if i == 'b':
				abc += ac + abc
				abc %= mod
			if i == 'c':
				abcc += abc + abcc
				abcc %= mod
		return abcc


class Solution:

	def fun(self, s):
		(a, ab, abc) = (0, 0, 0)
		mod = 1000000007
		for i in s:
			if i == 'a':
				a = (2 * a + 1) % mod
			elif i == 'b':
				ab = (2 * ab + a) % mod
			else:
				abc = (2 * abc + ab) % mod
		return abc


class Solution:

	def fun(self, s):
		a = b = c = 0
		for idx in range(len(s)):
			alphabet = s[idx]
			if alphabet == 'a':
				a = 2 * a + 1
			elif alphabet == 'b':
				b = 2 * b + a
			else:
				c = 2 * c + b
		return c % (10 ** 9 + 7)


class Solution:

	def fun(self, s):
		(a, ab, abc) = (0, 0, 0)
		mod = 10 ** 9 + 7
		for i in range(len(s)):
			if s[i] == 'a':
				a = (2 * a + 1) % mod
			elif s[i] == 'b':
				ab = (ab * 2 + a) % mod
			else:
				abc = (2 * abc + ab) % mod
		return abc


class Solution:

	def fun(self, s):
		(N, MOD) = (len(s), 10 ** 9 + 7)
		acnt = sum((1 for c in s if c == 'a'))
		(ans, avar, bvar, cvar) = (0, 0, 0, 0)
		for i in reversed(range(N)):
			x = s[i]
			if x == 'c':
				cvar = (2 * cvar + 1) % MOD
			elif x == 'b':
				bvar = (2 * bvar + cvar) % MOD
			else:
				acnt -= 1
				avar = 2 ** acnt % MOD
				ans = (ans + avar * bvar) % MOD
		return ans


class Solution:

	def fun(self, s):
		n = len(s)
		mod = 10 ** 9 + 7
		aCount = bCount = cCount = 0
		for i in range(n):
			if s[i] == 'a':
				aCount = (1 + 2 * aCount) % mod
			elif s[i] == 'b':
				bCount = (aCount + 2 * bCount) % mod
			else:
				cCount = (bCount + 2 * cCount) % mod
		return cCount


class Solution:

	def fun(self, s):
		dp = [[0 for i in range(len(s) + 1)] for j in range(3)]
		for i in range(1, len(dp[0])):
			if s[i - 1] == 'a':
				dp[0][i] = dp[0][i - 1] * 2 + 1
				dp[1][i] = dp[1][i - 1]
				dp[2][i] = dp[2][i - 1]
			elif s[i - 1] == 'b':
				dp[0][i] = dp[0][i - 1]
				dp[1][i] = dp[0][i] + dp[1][i - 1] * 2
				dp[2][i] = dp[2][i - 1]
			else:
				dp[0][i] = dp[0][i - 1]
				dp[1][i] = dp[1][i - 1]
				dp[2][i] = dp[2][i - 1] * 2 + dp[1][i]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def fun(self, s):
		mod = 1000000007
		aCount = 0
		bCount = 0
		cCount = 0
		for i in range(len(s)):
			if s[i] == 'a':
				aCount = (1 + 2 * aCount) % mod
			elif s[i] == 'b':
				bCount = (aCount + 2 * bCount) % mod
			elif s[i] == 'c':
				cCount = (bCount + 2 * cCount) % mod
		return cCount


class Solution:

	def fun(self, s):
		m = 10 ** 9 + 7
		aCount = 0
		bCount = 0
		cCount = 0
		for i in range(len(s)):
			if s[i] == 'a':
				aCount = 1 + 2 * aCount
			elif s[i] == 'b':
				bCount = aCount + 2 * bCount
			elif s[i] == 'c':
				cCount = bCount + 2 * cCount
		return cCount % m


class Solution:

	def fun(self, s):
		ca = 0
		cab = 0
		cabc = 0
		for i in range(len(s)):
			if s[i] == 'a':
				ca = (2 * ca + 1) % 1000000007
			elif s[i] == 'b':
				cab = (2 * cab + ca) % 1000000007
			else:
				cabc = (2 * cabc + cab) % 1000000007
		return cabc


class Solution:

	def fun(self, s):
		n = len(s)
		dp = [[0 for j in range(n + 1)] for i in range(4)]
		seq = ['a', 'b', 'c']
		mod = 1000000007
		for i in range(n + 1):
			dp[0][i] = 1
		for i in range(1, 4):
			for j in range(1, n + 1):
				if seq[i - 1] == s[j - 1]:
					dp[i][j] = (dp[i - 1][j - 1] + 2 * dp[i][j - 1]) % mod
				else:
					dp[i][j] = dp[i][j - 1]
		return dp[-1][-1]


class Solution:

	def fun(self, s):
		a = 0
		b = 0
		c = 0
		mod = pow(10, 9) + 7
		for i in s:
			if i == 'a':
				a = (2 * a + 1) % mod
			elif i == 'b':
				b = (2 * b + a) % mod
			else:
				c = (2 * c + b) % mod
		return c


class Solution:

	def fun(self, s):
		(a_cnt, b_cnt, c_cnt) = (0, 0, 0)
		for char in s:
			if char == 'a':
				a_cnt = 1 + 2 * a_cnt
			if char == 'b':
				b_cnt = a_cnt + 2 * b_cnt
			if char == 'c':
				c_cnt = b_cnt + 2 * c_cnt
		if a_cnt > 0 and b_cnt > 0 and (c_cnt > 0):
			return c_cnt % (10 ** 9 + 7)
		return 0


class Solution:

	def fun(self, string):
		result = self.solve(string)
		return result % 1000000007

	def solve(self, string):
		dp = [0 for i in range(3)]
		for current in string:
			if current == 'a':
				dp[0] = 2 * dp[0] + 1
			elif current == 'b':
				dp[1] = 2 * dp[1] + dp[0]
			elif current == 'c':
				dp[2] = 2 * dp[2] + dp[1]
		return dp[2]


class Solution:

	def fun(self, string):
		result = self.solve(string)
		return result % 1000000007

	def solve(self, string):
		a = b = c = 0
		for current in string:
			if current == 'a':
				a = 2 * a + 1
			elif current == 'b':
				b = 2 * b + a
			elif current == 'c':
				c = 2 * c + b
		return c


class Solution:

	def fun(self, s):
		a = ab = abc = 0
		mo = 1000000000.0 + 7
		for c in s:
			if c == 'a':
				a = (2 * a + 1) % mo
			elif c == 'b':
				ab = (2 * ab % mo + a) % mo
			else:
				abc = (2 * abc % mo + ab) % mo
		return int(abc)


class Solution:

	def fun(self, s):
		a = 0
		b = 0
		c = 0
		for i in range(len(s)):
			if s[i] == 'a':
				a = 1 + 2 * a
			elif s[i] == 'b':
				b = a + 2 * b
			else:
				c = b + 2 * c
		return c % 1000000007


MOD = int(1000000000.0 + 7)

class Solution:

	def fun(self, s):
		ss = [0, 0, 0]
		n = len(s)
		for i in range(n - 1, -1, -1):
			if s[i] == 'c':
				ss[2] = 2 * ss[2] + 1
				ss[2] %= MOD
			elif s[i] == 'b':
				ss[1] = 2 * ss[1] + ss[2]
				ss[1] %= MOD
			elif s[i] == 'a':
				ss[0] = 2 * ss[0] + ss[1]
				ss[0] %= MOD
		return ss[0]


class Solution:

	def fun(self, s):
		a = 0
		ab = 0
		abc = 0
		for i in s:
			if i == 'a':
				a = a + a + 1
			elif i == 'b':
				ab = ab + ab + a
			else:
				abc = abc + abc + ab
		return abc % (10 ** 9 + 7)


class Solution:

	def fun(self, s):
		m = 10 ** 9 + 7
		(ac, bc, cc) = (0, 0, 0)
		n = len(s)
		for i in range(n):
			if s[i] == 'a':
				ac = 1 + 2 * ac
			elif s[i] == 'b':
				bc = ac + 2 * bc
			elif s[i] == 'c':
				cc = bc + 2 * cc
		return cc % m


class Solution:

	def fun(self, s):
		(acount, bcount, ccount) = (0, 0, 0)
		mod = 1000000007
		for i in range(len(s)):
			if s[i] == 'a':
				acount += acount + 1
				acount = acount % mod
			elif s[i] == 'b':
				bcount += bcount + acount
				bcount = bcount % mod
			elif s[i] == 'c':
				ccount += ccount + bcount
				ccount = ccount % mod
		return ccount


class Solution:

	def fun(self, s):
		a_cnt = 0
		b_cnt = 0
		c_cnt = 0
		mod = 1000000007
		for i in range(len(s)):
			if s[i] == 'a':
				a_cnt += a_cnt + 1
				a_cnt = a_cnt % mod
			elif s[i] == 'b':
				b_cnt += a_cnt + b_cnt
				b_cnt = b_cnt % mod
			elif s[i] == 'c':
				c_cnt += b_cnt + c_cnt
				c_cnt = c_cnt % mod
		return c_cnt


class Solution:

	def fun(self, s):
		if len(s) == 1:
			return 0
		a_count = 0
		b_count = 0
		c_count = 0
		for i in range(len(s)):
			if s[i] == 'a':
				a_count = 1 + 2 * a_count
			elif s[i] == 'b':
				b_count = a_count + 2 * b_count
			elif s[i] == 'c':
				c_count = b_count + 2 * c_count
		return c_count % (10 ** 9 + 7)


class Solution:

	def fun(self, s):
		m = 1000000007
		mat = [[0], [0], [0]]
		for i in range(0, len(s)):
			if s[i] == 'a':
				mat[0].append((mat[0][-1] * 2 % m + 1) % m)
			if s[i] == 'b':
				mat[1].append((mat[1][-1] * 2 % m + mat[0][-1]) % m)
			if s[i] == 'c':
				mat[2].append((mat[2][-1] * 2 % m + mat[1][-1]) % m)
		return mat[-1][-1]


MOD = pow(10, 9) + 7

class Solution:

	def fun(self, s):
		a = ab = abc = 0
		for char in s:
			if char == 'a':
				a = (a + a + 1) % MOD
			elif char == 'b':
				ab = (ab + ab + a) % MOD
			elif char == 'c':
				abc = (abc + abc + ab) % MOD
		return abc


class Solution:

	def fun(self, s):
		ca = 0
		c_ab = 0
		c_abc = 0
		for i in range(len(s)):
			if s[i] == 'a':
				ca = 1 + 2 * ca
			elif s[i] == 'b':
				c_ab = ca + 2 * c_ab
			else:
				c_abc = (c_ab + 2 * c_abc) % (10 ** 9 + 7)
		return c_abc


class Solution:

	def fun(self, s):
		P = 10 ** 9 + 7
		ans = 0
		acount = 0
		bcount = 0
		ccount = 0
		for i in s:
			if i == 'a':
				acount = 1 + 2 * acount
			if i == 'b':
				bcount = acount + 2 * bcount
			if i == 'c':
				ccount = bcount + 2 * ccount
		ans = ccount
		return ans % P


import sys
sys.setrecursionlimit(10000)

class Solution:

	def __init__(self):
		self.memo = {}
		self.next = {'a': 'b', 'b': 'c', 'c': '0'}

	def helper(self, s, ch, start):
		if ch == '0':
			return 1
		if start == len(s):
			return 0
		key = (ch, start)
		if key in self.memo:
			return self.memo[key]
		if s[start] != ch:
			self.memo[key] = self.helper(s, ch, start + 1)
		else:
			self.memo[key] = 2 * self.helper(s, ch, start + 1) + self.helper(s, self.next[ch], start + 1)
		self.memo[key] %= int(10 ** 9 + 7.1)
		return self.memo[key]

	def fun(self, s):
		res = self.helper(s, 'a', 0)
		return res % int(10 ** 9 + 7.1)


class Solution:

	def fun(self, s):
		mod = 1000000007
		(a, b, c) = (0, 0, 0)
		for i in s:
			if i == 'a':
				a = (1 + 2 * a) % mod
			elif i == 'b':
				b = (a + 2 * b) % mod
			elif i == 'c':
				c = (b + 2 * c) % mod
		return c


class Solution:

	def fun(self, s):
		n = len(s)
		mod = 10 ** 9 + 7
		aa = 0
		bb = 0
		cc = 0
		for ele in s[::-1]:
			if ele == 'c':
				cc += cc
				cc += 1
				cc = cc % mod
			if ele == 'b':
				bb += bb
				bb += cc
				bb = bb % mod
			if ele == 'a':
				aa += aa
				aa += bb
				aa = aa % mod
		return aa


class Solution:

	def fun(self, s):
		n = len(s)
		dp = [[0] * (n + 1) for _ in range(4)]
		for i in range(n + 1):
			dp[0][i] = 1
		for i in range(1, 4):
			for j in range(1, n + 1):
				dp[i][j] = dp[i][j - 1]
				if ord(s[j - 1]) - 96 == i:
					dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + dp[i][j - 1]) % (10 ** 9 + 7)
		return dp[3][n]


class Solution:

	def fun(self, s):
		s1 = [0, 0, 0]
		i = len(s) - 1
		while i >= 0:
			if s[i] == 'c':
				s1[2] = (2 * s1[2] + 1) % 1000000007
			elif s[i] == 'b':
				s1[1] = (2 * s1[1] + s1[2]) % 1000000007
			else:
				s1[0] = (2 * s1[0] + s1[1]) % 1000000007
			i -= 1
		return s1[0]


class Solution:

	def fun(self, s):
		a = [0, 0, 0]
		for x in s[::-1]:
			if x == 'c':
				a[2] = (2 * a[2] + 1) % (10 ** 9 + 7)
			elif x == 'b':
				a[1] = (2 * a[1] + a[2]) % (10 ** 9 + 7)
			else:
				a[0] = (2 * a[0] + a[1]) % (10 ** 9 + 7)
		return a[0]


class Solution:

	def fun(self, s):
		mod = 10 ** 9 + 7
		(aCount, bCount, cCount) = (0, 0, 0)
		for c in s:
			if c == 'a':
				aCount = 2 * aCount + 1
			elif c == 'b':
				bCount = aCount + 2 * bCount
			else:
				cCount = bCount + 2 * cCount
		return cCount % mod


class Solution:

	def fun(self, s):
		(a, b, c) = (0, 0, 0)
		m = 1000000000.0 + 7
		for i in range(len(s)):
			if s[i] == 'a':
				a = int((2 * a + 1) % m)
			if s[i] == 'b':
				b = int((2 * b + a) % m)
			if s[i] == 'c':
				c = int((2 * c + b) % m)
		return c


from collections import defaultdict
modu = 1000000007

class Solution:

	def fun(self, s):
		myArr = defaultdict(lambda : defaultdict(lambda : 0))
		chars = ['a', 'b', 'c']
		for i in range(3):
			for j in range(len(s)):
				myArr[-1][j] = 1
				myArr[i][j] = (myArr[i][j - 1] % modu * (2 % modu) % modu + myArr[i - 1][j] % modu) % modu if s[j] == chars[i] else myArr[i][j - 1]
		return myArr[2][len(s) - 1]


class Solution:

	def fun(self, s):
		(a, b, c) = (0, 0, 0)
		MOD = 10 ** 9 + 7
		for ch in s:
			if ch == 'a':
				a = 2 * a + 1
			elif ch == 'b':
				b = 2 * b + a
			else:
				c = 2 * c + b
		return c % MOD
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


from functools import lru_cache

class Solution:

	def fun(self, s):
		dp = [[0] * 4 for _ in range(len(s) + 1)]
		dp[len(s)][3] = 1
		for i in range(len(s) - 1, -1, -1):
			for c in range(3, -1, -1):
				pick = 0
				if c == 0:
					if s[i] == 'a':
						pick += dp[i + 1][1]
				elif c == 1:
					if s[i] == 'a':
						pick += dp[i + 1][1]
					elif s[i] == 'b':
						pick += dp[i + 1][2]
				elif c == 2:
					if s[i] == 'b':
						pick += dp[i + 1][2]
					elif s[i] == 'c':
						pick += dp[i + 1][3]
				elif s[i] == 'c':
					pick += dp[i + 1][3]
				npick = dp[i + 1][c]
				dp[i][c] = pick + npick
		return dp[0][0] % (10 ** 9 + 7)
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


class Solution:

	def fun(self, s):
		sub_sequences = [0, 0, 0]
		i = len(s) - 1
		while i >= 0:
			if s[i] is 'c':
				sub_sequences[2] = (2 * sub_sequences[2] + 1) % 1000000007
			elif s[i] is 'b':
				sub_sequences[1] = (2 * sub_sequences[1] + sub_sequences[2]) % 1000000007
			elif s[i] is 'a':
				sub_sequences[0] = (2 * sub_sequences[0] + sub_sequences[1]) % 1000000007
			i = i - 1
		return sub_sequences[0]
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


class Solution:

	def fun(self, s):
		counta = 0
		countab = 0
		countabc = 0
		mod = 10 ** 9 + 7
		for i in range(len(s)):
			if s[i] == 'a':
				counta = (2 * counta + 1) % mod
			elif s[i] == 'b':
				countab = (2 * countab + counta) % mod
			elif s[i] == 'c':
				countabc = (2 * countabc + countab) % mod
		return countabc
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


class Solution:

	def fun(self, s):
		a = 0
		b = 0
		c = 0
		m = 10 ** 9 + 7
		n = len(s)
		for i in range(n):
			if s[i] == 'a':
				(a, b, c) = (2 * a + 1, b, c)
			elif s[i] == 'b':
				(a, b, c) = (a, 2 * b + a, c)
			else:
				(a, b, c) = (a, b, 2 * c + b)
			a = a % m
			b = b % m
			c = c % m
		return c
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


class Solution:

	def fun(self, s):
		a = 0
		ab = 0
		abc = 0
		for i in range(len(s)):
			ch = s[i]
			if ch == 'a':
				a = 2 * a + 1
			elif ch == 'b':
				ab = 2 * ab + a
			else:
				abc = 2 * abc + ab
		return abc % (10 ** 9 + 7)
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


class Solution:

	def fun(self, s):
		(a, ab, abc) = (0, 0, 0)
		mod = 1000000007
		for i in range(len(s)):
			if s[i] == 'a':
				a = (2 * a + 1) % mod
			elif s[i] == 'b':
				ab = (2 * ab + a) % mod
			elif s[i] == 'c':
				abc = (2 * abc + ab) % mod
		return abc
t = int(input())
for _ in range(t):
	s = input()
	print(Solution().fun(s))


mod = 10 ** 9 + 7

class Solution:

	def fun(self, s):
		a = 0
		ab = 0
		abc = 0
		for i in s:
			if i == 'a':
				a = (2 * a + 1) % mod
			if i == 'b':
				ab = (2 * ab + a) % mod
			if i == 'c':
				abc = (2 * abc + ab) % mod
		return abc % mod


class Solution:

	def fun(self, s):
		a = 0
		b = 0
		c = 0
		for char in s:
			if char == 'a':
				newa = 2 * a + 1
				a = newa
			if char == 'b':
				newb = 2 * b + a
				b = newb
			if char == 'c':
				newc = 2 * c + b
				c = newc
		return c % 1000000007


class Solution:

	def fun(self, s):
		(acount, bcount, ccount) = (0, 0, 0)
		for i in s:
			if i == 'a':
				acount = 1 + 2 * acount
			elif i == 'b':
				bcount = 2 * bcount + acount
			else:
				ccount = 2 * ccount + bcount
		return ccount % (10 ** 9 + 7)


mod = 10 ** 9 + 7

class Solution:

	def __init__(self):
		self.DP = []

	def solve(self, li, n):
		for i in range(0, n):
			for ended in range(0, 3):
				if i == 0:
					s = 1 if li[i] == ended and ended == 0 else 0
					self.DP[i][ended] = s
					continue
				if ended == 0:
					c = 1 if li[i] == ended else 0
					s = self.DP[i - 1][ended] + c * self.DP[i - 1][ended] + c
					self.DP[i][ended] = s % mod
					continue
				partial = 0
				if li[i] == ended:
					partial = self.DP[i - 1][ended - 1] + self.DP[i - 1][ended]
				s = partial + self.DP[i - 1][ended]
				self.DP[i][ended] = s % mod
		return self.DP[n - 1][2]

	def fun(self, s):
		self.DP = [[-1, -1, -1] for i in range(len(s) + 1)]
		li = [ord(i) - ord('a') for i in s]
		return self.solve(li, len(s))


class Solution:

	def fun(self, s):
		mod = 1000000007
		a = 0
		b = 0
		c = 0
		n = len(s)
		for i in range(n):
			if s[i] == 'a':
				a = (1 + 2 * a) % mod
			if s[i] == 'b':
				b = (a + 2 * b) % mod
			if s[i] == 'c':
				c = (b + 2 * c) % mod
		return c


class Solution:

	def fun(self, s):
		sa = 0
		sab = 0
		sabc = 0
		mod = 1000000000.0 + 7
		for i in range(0, len(s)):
			if s[i] == 'a':
				sa = 2 * sa + 1
			elif s[i] == 'b':
				sab = sa + 2 * sab
			elif s[i] == 'c':
				sabc = sab + 2 * sabc
			sa = sa % mod
			sab = sab % mod
			sabc = sabc % mod
		return int(sabc)


class Solution:

	def fun(self, s):
		a = 0
		ab = 0
		abc = 0
		for ch in s:
			if ch == 'a':
				a = 2 * a + 1
			elif ch == 'b':
				ab = 2 * ab + a
			elif ch == 'c':
				abc = 2 * abc + ab
		return abc % (10 ** 9 + 7)


class Solution:

	def fun(self, s):
		c = 0
		bc = 0
		ans = 0
		l = len(s)
		for i in range(l - 1, -1, -1):
			if s[i] == 'c':
				c = 2 * c + 1
			elif s[i] == 'b':
				bc = 2 * bc + c
			elif s[i] == 'a':
				ans = 2 * ans + bc
		return ans % 1000000007


class Solution:

	def fun(self, s):
		sub_sequences = [0, 0, 0]
		i = len(s) - 1
		while i >= 0:
			if s[i] is 'c':
				sub_sequences[2] = (2 * sub_sequences[2] + 1) % 1000000007
			elif s[i] is 'b':
				sub_sequences[1] = (2 * sub_sequences[1] + sub_sequences[2]) % 1000000007
			elif s[i] is 'a':
				sub_sequences[0] = (2 * sub_sequences[0] + sub_sequences[1]) % 1000000007
			i = i - 1
		return sub_sequences[0]


class Solution:

	def fun(self, s):
		MOD = 10 ** 9 + 7
		n = len(s)
		aCount = abCount = abcCount = 0
		for i in range(n):
			if s[i] == 'a':
				aCount = (1 + aCount * 2) % MOD
			elif s[i] == 'b':
				abCount = (aCount + abCount * 2) % MOD
			else:
				abcCount = (abCount + abcCount * 2) % MOD
		return abcCount


import sys

class Solution:

	def fun(self, s):
		mod = 1000000000.0 + 7
		acount = 0
		bcount = 0
		ccount = 0
		for i in range(len(s)):
			if s[i] == 'a':
				acount = (1 + 2 * acount % mod) % mod
			elif s[i] == 'b':
				bcount = (acount % mod + 2 * bcount % mod) % mod
			elif s[i] == 'c':
				ccount = (bcount % mod + 2 * ccount % mod) % mod
		return int(ccount)


class Solution:

	def fun(self, s):
		a = 0
		ab = 0
		abc = 0
		ln = len(s)
		for x in range(ln):
			if s[x] == 'a':
				a = (2 * a % 1000000007 + 1) % 1000000007
			elif s[x] == 'b':
				ab = (2 * ab % 1000000007 + a) % 1000000007
			else:
				abc = (2 * abc % 1000000007 + ab) % 1000000007
		return abc


class Solution:

	def fun(self, s):
		(a, b, c) = (0, 0, 0)
		M = 1000000007
		for x in s:
			if x == 'a':
				a = (2 * a + 1) % M
			elif x == 'b':
				b = (2 * b + a) % M
			else:
				c = (2 * c + b) % M
		return c


class Solution:

	def fun(self, s):
		_mod_ = 1000000007
		a = ab = abc = 0
		for c in s:
			if c == 'a':
				a = (2 * a % _mod_ + 1) % _mod_
			if c == 'b':
				ab = (2 * ab % _mod_ + a) % _mod_
			if c == 'c':
				abc = (2 * abc % _mod_ + ab) % _mod_
		return abc