Buggy python submission (verdict: Runtime Error):
def memo_rec(N):
    if N == 3:
        return 61
    L = ['A', 'T', 'G', 'C']
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(l1, l2, l3, k):
        s = l1 + l2 + l3
        if s in ["AGC", "ACG", "GAC"]:
            return 0
        if k == 1:
            if (l1 == 'A' and l2 == 'C') or (l1 == 'C' and l2 == 'G') or (l1 == 'G' and l3 == 'C') or (l2 == 'G' and l3 == 'C') or (l1 == 'G' and l2 == 'C'):
                return 3
            else:
                return 4
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(x, l1, l2, k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 3):
        ret = (ret + rec(s[0], s[1], s[2], N - 3)) % MOD
    return ret

N = int(input())
print(memo_rec(N))

Fixed submission:
import itertools
def memo_rec(N):
    if N == 3:
        return 61
    if N == 4:
        return 230
    L = "ATGC"
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(s, k):
        if s.count("AGC"):
            return 0
        for i in range(3):
            t1, t2 = s[i], s[i + 1]
            if (s[:i] + t2 + t1 + s[i+2:]).count("AGC"):
                return 0
        if k == 0:
            return 1
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(str(x + s[:3]), k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 4):
        t = ''
        for x in s:
            t += x
        ret = (ret + rec(t, N - 4)) % MOD
    return ret

N = int(input())
print(memo_rec(N))

Buggy python submission (verdict: Runtime Error):
import itertools

def memo_rec(N):
    L = ['A', 'T', 'G', 'C']
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(l1, l2, l3, k):
        s = l1 + l2 + l3
        if s in ["AGC", "ACG", "GAC"]:
            return 0
        if k == 1:
            if (l1 == 'A' and l2 == 'C') or (l1 == 'C' and l2 == 'G') or (l1 == 'G' and l3 == 'C') or (l2 == 'G' and l3 == 'C') or (l1 == 'G' and l2 == 'C'):
                return 3
            else:
                return 4
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(x, l1, l2, k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 3):
        ret = (ret + rec(s[0], s[1], s[2], N - 3)) % MOD
    return ret

N = int(input())
print(memo_rec(N))


Fixed submission:
import itertools
def memo_rec(N):
    if N == 3:
        return 61
    if N == 4:
        return 230
    L = "ATGC"
    MOD = 10 ** 9 + 7
    dic = {}
    def rec(s, k):
        if s.count("AGC"):
            return 0
        for i in range(3):
            t1, t2 = s[i], s[i + 1]
            if (s[:i] + t2 + t1 + s[i+2:]).count("AGC"):
                return 0
        if k == 0:
            return 1
        if s + str(k) in dic:
            return dic[s + str(k)]
        else:
            ret = 0
            for x in L:
                ret = (ret + rec(str(x + s[:3]), k - 1)) % MOD
            dic[s + str(k)] = ret
            return ret
    ret = 0
    for s in itertools.product(L, repeat = 4):
        t = ''
        for x in s:
            t += x
        ret = (ret + rec(t, N - 4)) % MOD
    return ret

N = int(input())
print(memo_rec(N))