You are given a string $s$ consisting of lowercase Latin letters "a", "b" and "c" and question marks "?".

Let the number of question marks in the string $s$ be $k$. Let's replace each question mark with one of the letters "a", "b" and "c". Here we can obtain all $3^{k}$ possible strings consisting only of letters "a", "b" and "c". For example, if $s = $"ac?b?c" then we can obtain the following strings: $[$"acabac", "acabbc", "acabcc", "acbbac", "acbbbc", "acbbcc", "accbac", "accbbc", "accbcc"$]$.

Your task is to count the total number of subsequences "abc" in all resulting strings. Since the answer can be very large, print it modulo $10^{9} + 7$.

A subsequence of the string $t$ is such a sequence that can be derived from the string $t$ after removing some (possibly, zero) number of letters without changing the order of remaining letters. For example, the string "baacbc" contains two subsequences "abc" — a subsequence consisting of letters at positions $(2, 5, 6)$ and a subsequence consisting of letters at positions $(3, 5, 6)$.


-----Input-----

The first line of the input contains one integer $n$ $(3 \le n \le 200\,000)$ — the length of $s$.

The second line of the input contains the string $s$ of length $n$ consisting of lowercase Latin letters "a", "b" and "c" and question marks"?".


-----Output-----

Print the total number of subsequences "abc" in all strings you can obtain if you replace all question marks with letters "a", "b" and "c", modulo $10^{9} + 7$.


-----Examples-----
Input
6
ac?b?c

Output
24

Input
7
???????

Output
2835

Input
9
cccbbbaaa

Output
0

Input
5
a???c

Output
46



-----Note-----

In the first example, we can obtain $9$ strings:  "acabac" — there are $2$ subsequences "abc",  "acabbc" — there are $4$ subsequences "abc",  "acabcc" — there are $4$ subsequences "abc",  "acbbac" — there are $2$ subsequences "abc",  "acbbbc" — there are $3$ subsequences "abc",  "acbbcc" — there are $4$ subsequences "abc",  "accbac" — there is $1$ subsequence "abc",  "accbbc" — there are $2$ subsequences "abc",  "accbcc" — there are $2$ subsequences "abc". 

So, there are $2 + 4 + 4 + 2 + 3 + 4 + 1 + 2 + 2 = 24$ subsequences "abc" in total.

Difficulty: introductory

Starter code:

Solutions:
def num(s):
    ans1 = [0]*n
    for q in range(n):
        ans1[q] = s[q] == 'a'
    sum1 = 0
    for q in range(n):
        w = sum1*(s[q] == 'b')
        sum1 += ans1[q]
        ans1[q] = w
    sum1 = 0
    for q in range(n):
        w = sum1*(s[q] == 'c')
        sum1 += ans1[q]
        ans1[q] = w
    sum1 = 0
    for q in range(n):
        sum1 += ans1[q]
    return sum1 % C


n = int(input())
s = list(input())
C, k = 10**9+7, 0
ans, ans1, deg = [0]*n, [0]*n, [1]
for q in range(n):
    deg.append(deg[-1]*3 % C)
    k += s[q] == '?'
if k == 0:
    print(num(s))
elif k == 1:
    ans = 0
    for q in range(n):
        if s[q] == '?':
            for q1 in ['a', 'b', 'c']:
                s[q] = q1
                ans += num(s)
            break
    print(ans % C)
elif k == 2:
    ans = 0
    ind1 = ind2 = -1
    for q in range(n):
        if s[q] == '?' and ind1 == -1:
            ind1 = q
        elif s[q] == '?':
            ind2 = q
    for q in ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']:
        s[ind1], s[ind2] = q[0], q[1]
        ans += num(s)
    print(ans % C)
else:
    ans = 0
    for q1 in ['???', '??c', '?b?', '?bc', 'a??', 'a?c', 'ab?', 'abc']:
        t = q1.count('?')
        ans1 = [0] * n
        for q in range(n):
            ans1[q] = (s[q] == q1[0])*deg[k-t]
        sum1 = 0
        for q in range(n):
            w = sum1 * (s[q] == q1[1])
            sum1 += ans1[q]
            ans1[q] = w % C
        sum1 = 0
        for q in range(n):
            w = sum1 * (s[q] == q1[2])
            sum1 += ans1[q]
            ans1[q] = w % C
        sum1 = 0
        for q in range(n):
            sum1 += ans1[q]
        ans += sum1
    print(ans % C)


from sys import stdin
input = stdin.readline


def num(s):
    ans1 = [0]*n
    for q in range(n):
        ans1[q] = s[q] == 'a'
    sum1 = 0
    for q in range(n):
        w = sum1*(s[q] == 'b')
        sum1 += ans1[q]
        ans1[q] = w
    sum1 = 0
    for q in range(n):
        w = sum1*(s[q] == 'c')
        sum1 += ans1[q]
        ans1[q] = w
    sum1 = 0
    for q in range(n):
        sum1 += ans1[q]
    return sum1 % C


def main():
    s = list(input())
    k = 0
    ans, ans1, deg = [0]*n, [0]*n, [1]
    for q in range(n):
        deg.append(deg[-1]*3 % C)
        k += s[q] == '?'
    if k == 0:
        print(num(s))
    elif k == 1:
        ans = 0
        for q in range(n):
            if s[q] == '?':
                for q1 in ['a', 'b', 'c']:
                    s[q] = q1
                    ans += num(s)
                break
        print(ans % C)
    elif k == 2:
        ans = 0
        ind1 = ind2 = -1
        for q in range(n):
            if s[q] == '?' and ind1 == -1:
                ind1 = q
            elif s[q] == '?':
                ind2 = q
        for q in ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']:
            s[ind1], s[ind2] = q[0], q[1]
            ans += num(s)
        print(ans % C)
    else:
        ans = 0
        for q1 in ['???', '??c', '?b?', '?bc', 'a??', 'a?c', 'ab?', 'abc']:
            t = q1.count('?')
            ans1 = [0] * n
            for q in range(n):
                ans1[q] = (s[q] == q1[0])*deg[k-t]
            sum1 = 0
            for q in range(n):
                w = sum1 * (s[q] == q1[1])
                sum1 += ans1[q]
                ans1[q] = w % C
            sum1 = 0
            for q in range(n):
                w = sum1 * (s[q] == q1[2])
                sum1 += ans1[q]
                ans1[q] = w % C
            sum1 = 0
            for q in range(n):
                sum1 += ans1[q]
            ans += sum1
        print(ans % C)


n = int(input())
C = 10**9+7
main()


def pow3(a):
    return 0 if a == -1 else p[a]


afdsfasdf = int(input())
s = list(input())
n = len(s)
mod = pow(10, 9) + 7
x = [[0] * 2 for _ in range(n - 1)]
y = [[0] * 2 for _ in range(n - 1)]
p = [1] * n
ans = 0
for i in range(1, n):
    p[i] = 3 * p[i - 1] % mod
for i in range(n - 2):
    if s[i] == "a":
        x[i + 1][0] = 1
    elif s[i] == "?":
        x[i + 1][1] = 1
    for j in range(2):
        x[i + 1][j] += x[i][j]
    k = n - i - 1
    if s[k] == "c":
        y[i + 1][0] = 1
    elif s[k] == "?":
        y[i + 1][1] = 1
    for j in range(2):
        y[i + 1][j] += y[i][j]
for i in range(n - 2):
    j, k = i + 1, n - i - 2
    if s[j] == "b" or s[j] == "?":
        c1 = (x[j][0] * pow3(x[j][1]) + x[j][1] * pow3(x[j][1] - 1)) % mod
        c2 = (y[k][0] * pow3(y[k][1]) + y[k][1] * pow3(y[k][1] - 1)) % mod
        ans += c1 * c2
        ans %= mod
print(ans)


MOD = 10**9+7
n = int(input())
s = input()

leftQ = [0 for i in range(n)]
rghtQ = [0 for i in range(n)]

leftA = [0 for i in range(n)]
rghtC = [0 for i in range(n)]

for i in range(1,n):
	leftQ[i] = leftQ[i-1] + (1 if s[i-1]=='?' else 0)
	leftA[i] = leftA[i-1] + (1 if s[i-1]=='a' else 0)

for i in range(n-2,-1,-1):
	rghtQ[i] = rghtQ[i+1] + (1 if s[i+1]=='?' else 0)
	rghtC[i] = rghtC[i+1] + (1 if s[i+1]=='c' else 0)

ans = 0
for i in range(n):
	if s[i]=='b' or s[i]=='?':
		ans += leftA[i]*rghtC[i]*pow(3,leftQ[i],MOD)*pow(3,rghtQ[i],MOD)
		if leftQ[i] > 0:
			ans += leftQ[i]*rghtC[i]*pow(3,leftQ[i]-1,MOD)*pow(3,rghtQ[i],MOD)
		if rghtQ[i] > 0:
			ans += leftA[i]*rghtQ[i]*pow(3,leftQ[i],MOD)*pow(3,rghtQ[i]-1,MOD)
		if leftQ[i] > 0 and rghtQ[i] > 0:
			ans += leftQ[i]*rghtQ[i]*pow(3,leftQ[i]-1,MOD)*pow(3,rghtQ[i]-1,MOD)
		ans %= MOD

print(ans)

MOD = 10**9 + 7


def main():
    N = int(input())
    S = input()

    pre_hatena = S[:1].count("?")
    a = S[:1].count("a")
    post_hatena = S[2:].count("?")
    c = S[2:].count("c")

    rev_3 = pow(3, MOD-2, MOD)
    ans = 0
    for i in range(1, N-1):
        if S[i] == "?" or S[i] == "b":
            pre_pow = pow(3, pre_hatena, MOD)
            pre = pre_pow * a + ((pre_pow * rev_3) % MOD) * pre_hatena
            post_pow = pow(3, post_hatena, MOD)
            post = post_pow * c + ((post_pow * rev_3) % MOD) * post_hatena
            ans += pre * post
            ans %= MOD
        if S[i] == "?":
            pre_hatena += 1
        if S[i] == "a":
            a += 1
        if S[i+1] == "?":
            post_hatena -= 1
        if S[i+1] == "c":
            c -= 1
    print(ans)


def __starting_point():
    main()

__starting_point()

n = int(input())
s = input()

dp_a = 0
dp_ab = 0
dp_abc = 0
hatena = 1

mod = 10**9 + 7

if s[0]=="a" or s[0]=="?":
    dp_a = 1
if s[0]=="?":
    hatena = 3

for i in range(1,n):
    if s[i]=="a":
        dp_a = (dp_a + hatena) % mod
    elif s[i]=="b":
        dp_ab = (dp_a + dp_ab) % mod
    elif s[i]=="c":
        dp_abc = (dp_ab + dp_abc) % mod
    else:
        dp_abc = (dp_ab + 3 * dp_abc) % mod
        dp_ab = (3 * dp_ab + dp_a) % mod
        dp_a = (3 * dp_a + hatena) % mod
        hatena = (hatena * 3) % mod

print(dp_abc)


import sys
readline = sys.stdin.readline

N = readline()
S = readline().strip()
mod = 10**9+7
dp = [1] + [0]*3
for s in S:
    dp1 = dp[:]
    if s == 'a':
        dp1[1] += dp[0]
    elif s == 'b':
        dp1[2] += dp[1]
    elif s == 'c':
        dp1[3] += dp[2]
    else:
        dp1[1] += dp[0]
        dp1[2] += dp[1]
        dp1[3] += dp[2]
        dp1[0] += 2*dp[0]
        dp1[1] += 2*dp[1]
        dp1[2] += 2*dp[2]
        dp1[3] += 2*dp[3]
    dp = [d % mod for d in dp1]
print(dp[-1])


mod = 10**9+7

n = int(input())

s = input()

em = 1
a = 0
ab = 0
abc = 0

for cur_c in s:
    new_em = 0
    new_a = 0
    new_ab = 0
    new_abc = 0
    
    opts = [cur_c]
    if cur_c=="?":
        opts = ['a', 'b', 'c']
        
    for c in opts:
        new_em += em
        new_a += a
        new_ab += ab
        new_abc += abc
        if c == 'a':
            new_a += em
        elif c == 'b':
            new_ab += a
        else:
            new_abc += ab
    em = new_em % mod
    a = new_a % mod
    ab = new_ab % mod
    abc = new_abc % mod

print(abc)            


mod = 10**9+7
N, = list(map(int, input().split()))
s = input().strip()
a=0
b=0
c=0
t=1
for i in range(N):
    if s[i] == "a":
        a=(a+t)%mod
    elif s[i] == "b":
        b=(b+a)%mod
    elif s[i] == "c":
        c=(c+b)%mod
    elif s[i] == "?":
        t,a,b,c = t*3%mod,(a*3+t)%mod,(b*3+a)%mod,(c*3+b)%mod
print(c)


n = int(input())
seq = input()
dp = [0, 0]
ans = 0
mod = int(1e9 + 7)
pat = 1
for i in seq:
    if i == 'a':
        dp[0] = (dp[0] + pat) % mod
    elif i == 'b':
        dp[1] += dp[0]
        dp[1] %= mod
    elif i == 'c':
        ans = (ans + dp[1]) % mod
    else :
        ans = (3 * ans + dp[1]) % mod
        dp[1] = (3 * dp[1] + dp[0]) % mod
        dp[0] = (3*dp[0] + pat) % mod
        pat = (3 * pat) % mod
print(ans)


MOD = 10 ** 9 + 7

n = int(input())
# (used ?) * 3 + cur 
dp = [0] * 12
qcnt = 0
for c in input():
    new_dp = dp.copy()
    if c == 'a':
        new_dp[0] += 1
        new_dp[0] %= MOD
    elif c == 'b':
        new_dp[1] += dp[0]
        new_dp[1] %= MOD
        new_dp[4] += dp[3]
        new_dp[4] %= MOD
        new_dp[7] += dp[6]
        new_dp[7] %= MOD
        new_dp[10] += dp[9]
        new_dp[10] %= MOD
    elif c == 'c':
        new_dp[2] += dp[1]
        new_dp[2] %= MOD
        new_dp[5] += dp[4]
        new_dp[5] %= MOD
        new_dp[8] += dp[7]
        new_dp[8] %= MOD
        new_dp[11] += dp[10]
        new_dp[11] %= MOD
    else:
        qcnt += 1
        new_dp[3] += 1
        for i in range(8):
            if i % 3 == 2:
                continue
            new_dp[i + 4] += dp[i]
            new_dp[i] %= MOD
    dp = new_dp
    # print(dp)

ans = 0
for i in range(4):
    if qcnt - i < 0:
        break
    tmp = pow(3, qcnt - i, MOD)
    tmp *= dp[2 + 3 * i]
    ans += tmp % MOD
    ans %= MOD
# print(dp[2::3])
print(ans)

# for _ in range(int(input())):
for _ in range(1):
    n = int(input())
    s = input()
    suf = [0] * n
    suf[n - 1] = int(s[-1] in 'c')
    suf1 = [0] * n
    suf1[n - 1] = int(s[-1] in '?')
    mod = 10**9 + 7
    m = s.count('?')
    tr0 = pow(3, m, mod)
    if m - 1 >= 0:
        tr1 = pow(3, m - 1, mod)
    else:
        tr1 = 0
    if m - 2 >= 0:
        tr2 = pow(3, m - 2, mod)
    else:
        tr2 = 0
    trob = pow(3, mod - 2, mod)
    for i in range(n - 2, -1, -1):
        suf[i] = suf[i + 1] + int(s[i] in 'c')
        suf1[i] = suf1[i + 1] + int(s[i] in '?')
    for i in range(0, n - 1):
        if s[i] not in 'b?':
            suf[i + 1] = 0
            suf1[i + 1] = 0
        if s[i] == '?':
            suf[i + 1] *= tr1
            suf1[i + 1] *= tr2
            suf[i + 1] %= mod
            suf1[i + 1] %= mod
        else:
            suf[i + 1] *= tr0
            suf[i + 1] %= mod
            suf1[i + 1] *= tr1
            suf1[i + 1] %= mod
    suf[0] = 0
    suf1[0] = 0
    ans = 0
    kek = 0
    for i in range(n - 2, -1, -1):
        if s[i] not in 'a?':
            kek += suf[i + 1]
            kek += suf1[i + 1]
            continue
        if s[i] in 'a':
            ans += kek
        else:
            lol = kek * trob % mod
            ans += lol
        kek += suf[i + 1]
        kek += suf1[i + 1]
        ans %= mod
    print(ans)


import sys,math
from collections import Counter,deque,defaultdict
from bisect import bisect_left,bisect_right 
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = sys.stdin.readline()
s = s[:n]
dp = [[0] * 4 for _ in range(n+1)]
dp[0][0] = 1
for i,x in enumerate(s):
    for j in range(4):
        if x == '?':
            dp[i+1][j] = dp[i][j] * 3
        else:
            dp[i+1][j] = dp[i][j]
    if x == 'a' or x == '?':
        dp[i+1][1] += dp[i][0]
    if x == 'b' or x == '?':
        dp[i+1][2] += dp[i][1]
    if x == 'c' or x == '?':
        dp[i+1][3] += dp[i][2]
    for j in range(4):
        dp[i+1][j] %= mod
print(dp[-1][-1])


import sys
input=sys.stdin.readline
def count(a, b):
    m = len(a)
    n = len(b)
    lookup = [[0] * (n + 1) for i in range(m + 1)]
    for i in range(n+1):
        lookup[0][i] = 0
    for i in range(m + 1):
        lookup[i][0] = 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                lookup[i][j] = lookup[i - 1][j - 1] + lookup[i - 1][j]
            else:
                lookup[i][j] = lookup[i - 1][j]

    return lookup[m][n]
n=int(input())
s=input()
ans=0
z=0
for i in s:
    if(i=='?'):
        z+=1
n1=count(s,"abc")
ans=ans+(pow(3,z,1000000007)*n1)

n1=count(s,"?bc")
if(z>=1):
    ans=ans+(pow(3,z-1,1000000007)*n1)
n1=count(s,"a?c")
if(z>=1):
    ans=ans+(pow(3,z-1,1000000007)*n1)
n1=count(s,"ab?")
if(z>=1):
    ans=ans+(pow(3,z-1,1000000007)*n1)
n1=count(s,"??c")
if(z>=2):
    ans=ans+(pow(3,z-2,1000000007)*n1)
n1=count(s,"a??")
if(z>=2):
    ans=ans+(pow(3,z-2,1000000007)*n1)
n1=count(s,"?b?")
if(z>=2):
    ans=ans+(pow(3,z-2,1000000007)*n1)
n1=count(s,"???")
if(z>=3):
    ans=ans+(pow(3,z-3,1000000007)*n1)
print(ans%1000000007)

l=int(input())
s=input()
mod=10**9+7
dp=[[0,0,0,0] for _ in range(l+1)]
for i in range(l,-1,-1):
  for j in range(3,-1,-1):
    if i==l:
      if j==3:
        dp[i][j]=1
      else:
        dp[i][j]=0
    else:
      if s[i]=='?':
        dp[i][j]=dp[i+1][j]*3
      else:
        dp[i][j]=dp[i+1][j]
      if j!=3 and (s[i]=='?' or s[i]==('abc'[j])):
        dp[i][j]+=dp[i+1][j+1]
    dp[i][j]%=mod
print(dp[0][0])

MOD = 10 ** 9 + 7


n = int(input())
s = input()

cnt = s.count('?')
# print(cnt)

a, ab, abc = 0, 0, 0
a2, ab2, abc2 = 0, 0, 0
a3, ab3, abc3 = 0, 0, 0
a4, ab4, abc4 = 0, 0, 0
for i in s:
    if i == 'a':
        a += 1
    elif i == 'b':
        ab += a
        ab2 += a2
    elif i == 'c':
        abc += ab
        abc2 += ab2
        abc3 += ab3
    else:
        a2, ab2, abc2, ab3, abc3, abc4 = a2 + 1, ab2 + a, abc2 + ab, ab3 + a2, abc3 + ab2, abc4 + ab3
    # print(a, ab, abc)
    # print(a2, ab2, abc2)
    # print(a3, ab3, abc3)
    # print(a4, ab4, abc4)
    # print('=========')


if cnt == 0:
    pass
elif cnt == 1:
    abc *= 3
elif cnt == 2:
    abc *= 9
    abc2 *= 3
elif cnt == 3:
    abc *= 27
    abc2 *= 9
    abc3 *= 3
else:
    abc = (abc * (3 ** cnt) % MOD) % MOD
    abc2 = (abc2 * (3 ** (cnt - 1)) % MOD) % MOD
    abc3 = (abc3 * (3 ** (cnt - 2)) % MOD) % MOD
    abc4 = (abc4 * (3 ** (cnt - 3)) % MOD) % MOD

# print(abc, abc2, abc3, abc4)

ans = (abc + abc2 + abc3 + abc4) % MOD
print(ans)


n = int(input())
s = str(input())

mod = 10**9+7

X = [[0]*4 for _ in range(n+1)]
for i in range(n):
    for j in range(4):
        X[i+1][j] = X[i][j]
    if s[i] == 'a':
        X[i+1][0] += 1
    elif s[i] == 'b':
        X[i+1][1] += 1
    elif s[i] == 'c':
        X[i+1][2] += 1
    else:
        X[i+1][3] += 1

Y = [[0]*4 for _ in range(n+1)]
for i in reversed(list(range(n))):
    for j in range(4):
        Y[i][j] = Y[i+1][j]
    if s[i] == 'a':
        Y[i][0] += 1
    elif s[i] == 'b':
        Y[i][1] += 1
    elif s[i] == 'c':
        Y[i][2] += 1
    else:
        Y[i][3] += 1
#print(X)
#print(Y)
c = X[n][3]
ans = 0
for i in range(n):
    if s[i] == 'b':
        ans += X[i+1][3]*Y[i][3]*pow(3, max(0, c-2), mod)
        ans += X[i+1][0]*Y[i][2]*pow(3, c, mod)
        ans += X[i+1][3]*Y[i][2]*pow(3, max(0, X[i+1][3]-1+Y[i][3]), mod)
        ans += X[i+1][0]*Y[i][3]*pow(3, max(0, X[i+1][3]+Y[i][3]-1), mod)
        ans %= mod
    if s[i] == '?':
        ans += X[i][3]*Y[i+1][3]*pow(3, max(0, c-3), mod)
        ans += X[i+1][0]*Y[i][2]*pow(3, max(0, c-1), mod)
        ans += X[i][3]*Y[i][2]*pow(3, max(0, X[i][3]-1+Y[i+1][3]), mod)
        ans += X[i+1][0]*Y[i+1][3]*pow(3, max(0, X[i][3]+Y[i+1][3]-1), mod)
        ans %= mod
        ans %= mod
print(ans)


from sys import stdin, stdout
MOD=10**9+7
def find(arr,N):
    R=[0,0,0]
    Z=1
    for i in arr:
        if i=='a': R[0]+=Z
        if i=='b': R[1]=(R[1]+R[0])%MOD
        if i=='c': R[2]=(R[2]+R[1])%MOD
        if i=='?':
            a,b,c=R[:],R[:],R[:]
            a[0]=(a[0]+Z)%MOD
            b[1]=(b[1]+b[0])%MOD
            c[2]=(c[2]+c[1])%MOD
            R=[(a[i]+b[i]+c[i])%MOD for i in range(3)]
            Z=Z*3%MOD
            # print(a)
            # print(b)
            # print(c)
        # print(R)
    return R[2]%MOD

def main():
    # for _ in range(int(stdin.readline())):
        N=int(stdin.readline())
        arr=stdin.readline().strip()
        print(find(arr,N))
main()


# H=[]
# def bt(i,s):
#     if i==2: 
#         return H.append(s)
#     bt(i+1,s+"a")
#     bt(i+1,s+"b")
#     bt(i+1,s+"c")
# bt(0,"")
# print(H)
# F=0
# X=[0,0,0]
# for j in H:
#     R=[0,0,0]
#     for i in j:
#         if i=='a': R[0]+=1
#         if i=='b': R[1]+=R[0]
#         if i=='c': R[2]+=R[1]
#     F+=R[2]
#     X=[X[i]+R[i] for i in range(3)]
# print(X)
# print(F)


import sys
input = sys.stdin.readline

n=int(input())
S=input().strip()

mod=10**9+7

A=0
AB=0
ABC=0
q=0

for s in S:
    if s=="a":
        A+=pow(3,q,mod)
    elif s=="b":
        AB+=A
    elif s=="c":
        ABC+=AB
    else:
        ABC=AB+ABC*3
        AB=A+AB*3
        A=pow(3,q,mod)+A*3
        q+=1
    A%=mod
    AB%=mod
    ABC%=mod
    
print(ABC)


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

N = INT()
S = input()

dp0 = [0] * (N+1)
dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
dp3 = [0] * (N+1)
dp0[0] = 1
for i in range(N):
    if S[i] == 'a':
        dp0[i+1] += dp0[i]
        dp1[i+1] += dp1[i]
        dp2[i+1] += dp2[i]
        dp3[i+1] += dp3[i]
        dp1[i+1] += dp0[i]
    elif S[i] == 'b':
        dp0[i+1] += dp0[i]
        dp1[i+1] += dp1[i]
        dp2[i+1] += dp2[i]
        dp3[i+1] += dp3[i]
        dp2[i+1] += dp1[i]
    elif S[i] == 'c':
        dp0[i+1] += dp0[i]
        dp1[i+1] += dp1[i]
        dp2[i+1] += dp2[i]
        dp3[i+1] += dp3[i]
        dp3[i+1] += dp2[i]
    else:
        dp0[i+1] += dp0[i]*3
        dp1[i+1] += dp1[i]*3
        dp2[i+1] += dp2[i]*3
        dp3[i+1] += dp3[i]*3
        dp1[i+1] += dp0[i]
        dp2[i+1] += dp1[i]
        dp3[i+1] += dp2[i]
    dp0[i+1] %= MOD
    dp1[i+1] %= MOD
    dp2[i+1] %= MOD
    dp3[i+1] %= MOD
ans = dp3[N]
print(ans)


n=int(input())
s=input()
MOD=10**9+7
numa=0
numab=0
ans=0
numa1=0
numab1=0
ans1=0
numab2=0
ans2=0
ans3=0
count=0
for i in range(n):
    if s[i]=='a':
        numa=(numa+1)%MOD
    elif s[i]=='b':
        numab=(numab+numa)%MOD
        numab1=(numab1+numa1)%MOD
    elif s[i]=='c':
        ans=(ans+numab)%MOD
        ans1=(ans1+numab1)%MOD
        ans2=(ans2+numab2)%MOD
    else:
        ans1=(ans1+numab)%MOD
        ans2=(ans2+numab1)%MOD
        ans3=(ans3+numab2)%MOD
        numab1=(numab1+numa)%MOD
        numab2=(numab2+numa1)%MOD
        numa1=(numa1+1)%MOD
        count+=1
ans=(ans*pow(3,count,MOD))%MOD
if count>=3:
    ans=(ans+ans3*pow(3,count-3,MOD))%MOD
if count>=2:
    ans=(ans+ans2*pow(3,count-2,MOD))%MOD
if count>=1:
    ans=(ans+ans1*pow(3,count-1,MOD))%MOD
print(ans)

n=int(input())
s=input()
dp=[[0,0,0]for i in range(n)]
ct=1
mod=10**9+7
for i in range(n):
    if i==0:
        if s[i]=='?':ct*=3
        if s[i]=='a' or s[i]=='?':dp[i][0]+=1
    else:
        aa,bb,cc=dp[i-1]
        if s[i]=='a':
            dp[i][0]=aa+ct
            dp[i][1]=bb
            dp[i][2]=cc
        if s[i]=='b':
            dp[i][0]=aa
            dp[i][1]=aa+bb
            dp[i][2]=cc
        if s[i]=='c':
            dp[i][0]=aa
            dp[i][1]=bb
            dp[i][2]=bb+cc
        if s[i]=='?':
            dp[i][0]=aa*3+ct
            dp[i][1]=bb*3+aa
            dp[i][2]=cc*3+bb
            ct*=3
    ct%=mod
    dp[i][0]%=mod
    dp[i][1]%=mod
    dp[i][2]%=mod
print(dp[-1][-1])

from bisect import *
from collections import *
from math import *
from heapq import *
from typing import List
from itertools import *
from operator import *
from functools import *
import sys
'''
@lru_cache(None)
def fact(x):
    if x<2:
        return 1
    return fact(x-1)*x

@lru_cache(None)
def per(i,j):
    return fact(i)//fact(i-j)

@lru_cache(None)
def com(i,j):
    return per(i,j)//fact(j)

def linc(f,t,l,r):
    while l<r:
        mid=(l+r)//2
        if t>f(mid):
            l=mid+1
        else:
            r=mid
    return l

def rinc(f,t,l,r):
    while l<r:
        mid=(l+r+1)//2
        if t<f(mid):
            r=mid-1
        else:
            l=mid
    return l

def ldec(f,t,l,r):
    while l<r:
        mid=(l+r)//2
        if t<f(mid):
            l=mid+1
        else:
            r=mid
    return l

def rdec(f,t,l,r):
    while l<r:
        mid=(l+r+1)//2
        if t>f(mid):
            r=mid-1
        else:
            l=mid
    return l

def isprime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def power2(n):
    while not n&1:
        n>>=1
    return n==1
'''
'''
for i in range(t):
    #n,m=map(int,input().split())
    n,m=1,0
    graph=defaultdict(set)
    for i in range(m):
        u,v=map(int,input().split())
        graph[u-1].add(v-1)
    visited=[0]*n
    ans=[]
    def delchild(u):
        for child in graph[u]:
            visited[child]=1
            ans.append(child+1)
    for i in range(n):
        if not visited[i]:
            children=graph[i]
            if len(children)==1:
                u=children.pop()
                visited[u]=1
                delchild(u)
            elif len(children)==2:
                u=children.pop()
                v=children.pop()
                if u in graph[v]:
                    delchild(v)
                    visited[v]=1
                elif v in graph[u]:
                    delchild(u)
                    visited[u]=1
                else:
                    delchild(u)
                    delchild(v)
                    visited[u]=visited[v]=1
    print(len(ans))
    sys.stdout.flush()
    print(' '.join(map(str,ans)))
    sys.stdout.flush()

import time
s=time.time()
e=time.time()
print(e-s)
'''
'''
t=int(input())
for i in range(t):
    #n,m=map(int,input().split())
    n=int(input())
    x=int(sqrt(n))
    if x*x==n:
        ans=2*x-2
    elif x*(x+1)>=n:
        ans=2*x-1
    else:
        ans=2*x
    print(ans)
'''
n=int(input())
arr=input()
mod=10**9+7
a=b=c=0
x=1
for ch in arr:
    #print(ch,a,b,c)
    if ch=='a':
        a=(a+x)%mod
    elif ch=='b':
        b=(b+a)%mod
    elif ch=='c':
        c=(c+b)%mod
    else:
        a,b,c=(3*a+x)%mod,(3*b+a)%mod,(3*c+b)%mod
        x=(3*x)%mod
print(c)

    



n = int(input())
s = " " + input()
F = [[-1 for i in range(4)] for j in range(n + 1)]
F[0] = [1, 0, 0, 0]

div = (10 ** 9 + 7)

for i in range(1, n + 1):
    if s[i] == "?":
        F[i][0] = (3 * F[i-1][0]) % div
    else:
        F[i][0] = F[i-1][0] % div
    
    if s[i] == "a":
        F[i][1] = (F[i-1][1] + F[i-1][0]) % div
    elif s[i] == "?":
        F[i][1] = (3 * F[i-1][1] + F[i-1][0]) % div
    else:
        F[i][1] = (F[i-1][1]) % div
    
    if s[i] == "b":
        F[i][2] = (F[i-1][2] + F[i-1][1]) % div
    elif s[i] == "?":
        F[i][2] = (3 * F[i-1][2] + F[i-1][1]) % div
    else:
        F[i][2] = F[i-1][2] % div
    
    if s[i] == "c":
        F[i][3] = (F[i-1][3] + F[i-1][2]) % div
    elif s[i] == "?":
        F[i][3] = (3 * F[i-1][3] + F[i-1][2])  % div
    else:
        F[i][3] = F[i-1][3] % div
    

print(F[-1][3])

def main():
    #n, m = map(int, input().split())

    n = int(input())
    s = input()
    
    a, b, ans = 0, 0, 0
    cnt = 1
    for i in range(n):
        if s[i] == "?":
            ans = (ans*3 + b) % 1000_000_007
            b = (b * 3 + a) % 1000_000_007
            a = (a * 3 + cnt) % 1000_000_007
            cnt = (cnt * 3) % 1000_000_007
        elif s[i] == "c":
            ans = (ans + b) % 1000_000_007
        elif s[i] == "b":
            b = (b + a) % 1000_000_007
        elif s[i] == "a":
            a = (a + cnt) % 1000_000_007
    print(ans)

#input = sys.stdin.readline

#sys.setrecursionlimit(2097152)
tn = 1 #int(input())
for _ in range(tn):
    main()

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



n = val()
l = list(st())





questions1 = [0]
As = [0]
Cs = [0]
questions2 = [0]

for i in range(n):

    questions1.append(questions1[-1])
    if l[i] == '?':
        questions1[-1] += 1
        
    
    As.append(As[-1])
    if l[i] == 'a':
        As[-1] += 1

for i in range(n - 1, -1, -1):
    questions2.append(questions2[-1])
    if l[i] == '?':
        questions2[-1] += 1
        
    
    Cs.append(Cs[-1])
    if l[i] == 'c':
        Cs[-1] += 1

Cs.pop()
questions2.pop()

Cs.reverse()
questions2.reverse()


ans = 0
for i in range(n):
    if l[i] == 'b' or l[i] == '?':
        left = right = 0
        left = As[i] * pow(3, questions1[i], mod) % mod
        if questions1[i]:left = (left + pow(3, questions1[i] - 1, mod) * questions1[i]) % mod
        right = Cs[i] * pow(3, questions2[i], mod) % mod
        if questions2[i]:right = (right + pow(3, questions2[i] - 1, mod) * questions2[i]) % mod

        # print(l, i, left, right)

        ans = (ans + left * right) % mod
print(ans)

mod = 10 ** 9 + 7
n = int(input())
s = input()
dp = [[0] * 4 for i in range(len(s) + 1)]
dp[len(s)][3] = 1
for i in range(len(s))[::-1]:
    for j in range(4)[::-1]:
        if s[i] == "?":
            dp[i][j] = dp[i + 1][j] * 3
        else:
            dp[i][j] = dp[i + 1][j]
        if j < 3:
            if s[i] == "?" or s[i] == "abc"[j]:
                dp[i][j] += dp[i + 1][j + 1]
        dp[i][j] %= mod
print(dp[0][0])

n = int(input())
s = input().lower()

dp_a = 0
dp_ab = 0
dp_abc = 0
hatena = 1

mod = 10**9 + 7

for i in range(n):
    if s[i]=="a":
        dp_a = (dp_a + hatena) % mod
    elif s[i]=="b":
        dp_ab = (dp_a + dp_ab) % mod
    elif s[i]=="c":
        dp_abc = (dp_ab + dp_abc) % mod
    else:
        dp_abc = (dp_ab + 3 * dp_abc) % mod
        dp_ab = (3 * dp_ab + dp_a) % mod
        dp_a = (3 * dp_a + hatena) % mod
        hatena = (hatena * 3) % mod

print(dp_abc)


n = int(input());seq = input();dp = [0, 0];ans = 0;mod = int(1e9 + 7);pat = 1
for i in seq:
    if i == 'a':dp[0] = (dp[0] + pat) % mod
    elif i == 'b':dp[1] += dp[0];dp[1] %= mod
    elif i == 'c':ans = (ans + dp[1]) % mod
    else :ans = (3 * ans + dp[1]) % mod;dp[1] = (3 * dp[1] + dp[0]) % mod;dp[0] = (3*dp[0] + pat) % mod;pat = (3 * pat) % mod
print(ans)

n = int(input())
s = input()

dp = [[0, 0, 0] for _ in range(n)]
dp2 = [[0, 0, 0] for _ in range(n)]
prev = [0, 0, 0]
free = 0

mod = 1000000007
for i in range(n):
	if i > 0:
		dp[i] = dp[i-1].copy()
	if s[i] == 'a':
		dp[i][0] += 1
	if s[i] == 'b':
		dp[i][1] += dp[i][0]
		if dp[i][1] >= mod:
			dp[i][1] -= mod
	if s[i] == 'c':
		dp[i][2] += dp[i][1]
		if dp[i][2] >= mod:
			dp[i][2] -= mod
	if s[i] == '?':
		free += 1

for i in reversed(range(0, n)):
	if i+1 < n:
		dp2[i] = dp2[i+1].copy()
	if s[i] == 'c':
		dp2[i][0] += 1
	if s[i] == 'b':
		dp2[i][1] += dp2[i][0]
		if dp2[i][1] >= mod:
			dp2[i][1] -= mod
	if s[i] == 'a':
		dp2[i][2] += dp2[i][1]
		if dp2[i][2] >= mod:
			dp2[i][2] -= mod

ans = dp[n-1][2] * pow(3, free, mod) % mod
ans += (free*(free-1)*(free-2)//6) * pow(3, mod-1+free-3, mod) % mod
before, after = 0, free
for i in range(n):
	if s[i] == '?':
		mul = pow(3, free-1, mod)
		ans += mul*(dp[i][0] * dp2[i][0] + dp2[i][1] + dp[i][1]) % mod
		before += 1
		after -= 1
	if s[i] == 'a':
		ans += pow(3, mod-1+free-2, mod) * (after*(after-1)//2) % mod
	if s[i] == 'b':
		ans += pow(3, mod-1+free-2, mod) * (after * before)%mod
	if s[i] == 'c':
		ans += pow(3, mod-1+free-2, mod) * (before*(before-1)//2) % mod
	if ans >= mod:
		ans %= mod
print(ans%mod)