Problem p03291 (python)

Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    # c の個数
    n = [0 for c in S]
    for i in range(1, len(S)):
        n[i] = n[i-1] + (1 if S[i-1] == c else 0)
 
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n)):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
def nright(S, c):
    # c の個数
    n = [0 for c in S]
    for i in range(len(S) - 1, 0, -1):
        n[i-1] = n[i] + (1 if S[i] == c else 0)
 
    q = 0      # '?'の個数
    pow3q = 1  # 3 ** q
    for i in range(len(n) - 1, -1, -1):
        if q > 0:
            n[i] *= pow3q         # ?の埋め方の数だけ増やす
            n[i] += pow3q1 * q    # ?に入る'C'の個数
            n[i] %= modulo
        if S[i] == '?':
            q += 1
            pow3q1 = pow3q
            pow3q  = pow3q * 3 % modulo
    return n
 
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
modulo = 10 ** 9 + 7
 
S = input()
 
def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """
 
    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n
 
    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')
 
    for i in range(len(n)):
        n[i] *= (3 ** q[i]) % modulo               # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i] % modulo  # ?に入る'C'の個数
    return n
 
def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n
 
left  = nleft (S, 'A')
right = nright(S, 'C')
 
# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]
 
abc = int(abc) % modulo
print(abc)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

modulo = 10 ** 9 + 7

S = input()

def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """

    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n

    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')

    for i in range(len(n)):
        n[i] *= (3 ** q[i]) % modulo               # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i] % modulo  # ?に入る'C'の個数
        n[i] %= modulo
    return n

def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n

left  = nleft (S, 'A')
right = nright(S, 'C')

# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]

abc = int(abc) % modulo
print(abc)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

S = input()

def nleft(S, c):
    """各位置について，それより左の文字列に含まれる文字 c の総数.
       左に'?'が含まれるときは，それらに文字を入れて得られるすべての
       文字列に渡って，文字 c の個数を合計する. """

    def _left(S, c):
        """各位置より左にある c の個数. """
        n = [0 for c in S]
        for i in range(1, len(n)):
            n[i] = n[i-1] + (1 if S[i-1] == c else 0)
        return n

    # c の個数, '?'の個数
    n = _left(S, c)
    q = _left(S, '?')

    for i in range(len(n)):
        n[i] *= 3 ** q[i]                 # ?の埋め方の数だけ増やす
        n[i] += (3 ** (q[i] - 1)) * q[i]  # ?に入る'C'の個数
    return n

def nright(S, c):
    n = nleft(list(reversed(S)), c)
    n.reverse()
    return n

left  = nleft (S, 'A')
right = nright(S, 'C')

# 各文字が'B'のときのABC数を計算
abc = 0
for i in range(0, len(S)):
    if S[i] in 'B?':
        abc += left[i] * right[i]

abc = int(abc) % (10 ** 9 + 7)
print(abc)