Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys

S=sys.stdin.readline().strip()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: nan-mojime,  j=0:All mojiretsu pattern , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print ( dp[(l,3)]%mod )




Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys

S=sys.stdin.readline().strip()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: nan-mojime,  j=0:All mojiretsu pattern , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print dp[(l,3)]%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

S=raw_input()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: i-mojime,  j=0:None , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

n=0
cnt=0	# count of "?"
for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print dp[(l,3)]%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
 
M=10**9+7
 
a=0
ab=0
ans=0
all=1
 
for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3
 
	ans%=M
	ab%=M
	a%=M
	all%M
 
 
print ans%M

Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys
S=sys.stdin.readline()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		ans+=ab
	if x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys
S=sys.stdin.readline()

M=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=M
	ab%=M
	a%=M
	all%M


print ans%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys
S=sys.stdin.readline()

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys

S=sys.stdin.readline()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys

S=sys.stdin.readline()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for x  in S:
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys

S=sys.stdin.readline()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i,x  in enumerate(S):
	if x=="A":
		a+=all
	elif x=="B":
		ab+=a
	elif x=="C":
		ans+=ab
	elif x=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
import sys

S=sys.stdin.readline()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print (ans)


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
l=len(S)

mod=10**9+7

a=0
ab=0
ans=0
all=1

for i in range(l):
	if S[i]=="A":
		a+=all
	elif S[i]=="B":
		ab+=a
	elif S[i]=="C":
		ans+=ab
	elif S[i]=="?":
		ans = ans*3 + ab
		ab = ab*3 + a
		a = a*3 + all
		all *= 3

	ans%=mod
	ab%=mod
	a%=mod
	all%mod


print ans


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
l=len(S)

mod=10**9+7

dp=[ 0  for j in range(4) ] 

all=1  #Joutai-su

for i in range(l):
	t1=dp[1]
	t2=dp[2]
	t3=dp[3]

	if S[i]=="A":
		dp[1]+=all
	elif S[i]=="B":
		dp[2]=t2+t1
	elif S[i]=="C":
		dp[3]=t3+t2
	elif S[i]=="?":
		dp[1]=t1*3+all
		dp[2]=t2*3+t1
		dp[3]=t3*3+t2
		all*=3

	dp[1]%=mod
	dp[2]%=mod
	dp[3]%=mod
	all%mod


print dp[-1]%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3

	dp[i][1]%=mod
	dp[i][2]%=mod
	dp[i][3]%=mod
	all%mod


print dp[-1][-1]%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3

	dp[i][1]%=mod
	dp[i][2]%=mod
	dp[i][3]%=mod


print dp[-1][-1]%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=" "+raw_input()
l=len(S)

mod=10**9+7

dp=[  [ 0  for j in range(4) ]   for i in range(l) ] 

for i in range(l):
	dp[i][0]=1


all=1  #Joutai-su

for i in range(1,l):

	if S[i]=="A":
		dp[i][1]+=dp[i-1][1]+all
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="B":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]
	elif S[i]=="C":
		dp[i][1]+=dp[i-1][1]
		dp[i][2]+=dp[i-1][2]
		dp[i][3]+=dp[i-1][3]+dp[i-1][2]
	elif S[i]=="?":
		dp[i][1]+=dp[i-1][1]*3+all
		dp[i][2]+=dp[i-1][2]*3+dp[i-1][1]
		dp[i][3]+=dp[i-1][3]*3+dp[i-1][2]
		all*=3


print dp[-1][-1]%mod


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
L=len(S)
 
M=10**9+7
 
dp=[ [ 0 for i in range(4) ] for k in range(L+1)]
all=1
 
for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=( dp[i][1]+all ) %M
		dp[i+1][2]=dp[i][2]%M
		dp[i+1][3]=dp[i][3]%M
	if S[i]=="B":
		dp[i+1][2]=( dp[i][2]+dp[i][1] )%M
		dp[i+1][3]=dp[i][3]%M
		dp[i+1][1]=dp[i][1]%M
	if S[i]=="C":
		dp[i+1][3]=( dp[i][3]+dp[i][2] )%M
		dp[i+1][2]=dp[i][2]%M
		dp[i+1][1]=dp[i][1]%M
 
	if S[i]=="?":
		dp[i+1][1]=( dp[i][1]*3+all )%M
		dp[i+1][2]=( dp[i][2]*3+dp[i][1] )%M
		dp[i+1][3]=( dp[i][3]*3+dp[i][2] )%M
		all*=3	
 
print ( dp[-1][3] ) %M

Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)%mod

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )%mod

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)%mod

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )%mod

print ans%mod



Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )

print ans%mod



Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=dp[i][1]+all
		dp[i+1][2]=dp[i][2]
		dp[i+1][3]=dp[i][3]
	if S[i]=="B":
		dp[i+1][2]=dp[i][2]+dp[i][1]
		dp[i+1][3]=dp[i][3]
		dp[i+1][1]=dp[i][1]
	if S[i]=="C":
		dp[i+1][3]+=dp[i][3]+dp[i][2]
		dp[i+1][2]=dp[i][2]
		dp[i+1][1]=dp[i][1]

	if S[i]=="?":
		dp[i+1][1]=dp[i][1]*3+all
		dp[i+1][2]=dp[i][2]*3+dp[i][1]
		dp[i+1][3]=dp[i][3]*3+dp[i][2]
		all*=3

	dp[i+1][1]%=M
	dp[i+1][2]%=M
	dp[i+1][3]%=M
	all%M

print ( dp[-1][3] ) %M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Runtime Error):
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	ans%=M


print abc%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M


print abc%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M


print abc%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a=( a+all ) %M
	if x=="B":
		ab=( ab+a )%M
	if x=="C":
		abc=( abc+ab )%M

	if x=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print abc%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

abc=0
ab=0
a=0

for i in range(L):
	if S[i]=="A":
		a=( a+all ) %M
	if S[i]=="B":
		ab=( ab+a )%M
	if S[i]=="C":
		abc=( abc+ab )%M

	if S[i]=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print (abc%M)


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1) ]
all=1

abc=0
ab=0
a=0

for i in range(L):
	if S[i]=="A":
		a=( a+all ) %M
	if S[i]=="B":
		ab=( ab+a )%M
	if S[i]=="C":
		abc=( abc+ab )%M

	if S[i]=="?":
		abc=( abc*3+ab )%M
		ab=( ab*3+a)%M
		a=( a*3+all )%M
		all*=3

print abc%M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M

Buggy python submission (verdict: Time Limit Exceeded):
S=raw_input()
L=len(S)

M=10**9+7

dp=[ [ 0 for i in range(4) ] for k in range(L+1)]
all=1

for i in range(L):
	if S[i]=="A":
		dp[i+1][1]=( dp[i][1]+all ) %M
		dp[i+1][2]=dp[i][2]
		dp[i+1][3]=dp[i][3]
	if S[i]=="B":
		dp[i+1][2]=( dp[i][2]+dp[i][1] )%M
		dp[i+1][3]=dp[i][3]
		dp[i+1][1]=dp[i][1]
	if S[i]=="C":
		dp[i+1][3]=( dp[i][3]+dp[i][2] )%M
		dp[i+1][2]=dp[i][2]
		dp[i+1][1]=dp[i][1]

	if S[i]=="?":
		dp[i+1][1]=( dp[i][1]*3+all )%M
		dp[i+1][2]=( dp[i][2]*3+dp[i][1] )%M
		dp[i+1][3]=( dp[i][3]*3+dp[i][2] )%M
		all*=3	

print ( dp[-1][3] ) %M


Fixed submission:
S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M