Problem p03291 (python)

Fixed submission:
import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

dp = [[0] * (N + 1) for _ in range(4)]

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD

print(dp[3][N] % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

MOD = (10 ** 9) + 7
# import re

# input = sys.stdin.readline
sys.setrecursionlimit(10000)

S = input()
N = len(S)


def funcA(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "A" or S[idx] == "?":
        ret += funcB(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcA(idx + 1, q)
    return ret


def funcB(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "B" or S[idx] == "?":
        ret += funcC(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcB(idx + 1, q)
    return ret


def funcC(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "C" or S[idx] == "?":
        addQ = S[idx + 1:].count("?")
        ret += 3 ** (q + addQ)

    q += 1 if S[idx] == "?" else 0
    ret += funcC(idx + 1, q)
    return ret


ans = funcA(0, 0)

print(ans % MOD)

Buggy submission (verdict: Runtime Error):
import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

MOD = (10 ** 9) + 7
# import re

# input = sys.stdin.readline

S = input()
N = len(S)


def funcA(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "A" or S[idx] == "?":
        ret += funcB(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcA(idx + 1, q)
    return ret


def funcB(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "B" or S[idx] == "?":
        ret += funcC(idx + 1, q)
    q += 1 if S[idx] == "?" else 0
    ret += funcB(idx + 1, q)
    return ret


def funcC(idx, q):
    if idx >= N:
        return 0
    ret = 0
    if S[idx] == "C" or S[idx] == "?":
        addQ = S[idx + 1:].count("?")
        ret += 3 ** (q + addQ)

    q += 1 if S[idx] == "?" else 0
    ret += funcC(idx + 1, q)
    return ret


ans = funcA(0, 0)

print(ans % MOD)