Сколько различных читаемых последовательностей длины N существует?

def forr(st,st2):
    if "GG" in st2 or "AA" in st2 or "GT" in st2 or "GC" in st2 or "TG" in st2 or "TT" in st2 or "TC" in st2 or "CG" in st2 or "CT" in st2 or "CC" in st2:
        return 0
    else:
        return 1
def productt(*args, repeat=1):
    pools = [(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield (prod)
 
 
n=int(input())
a=["G","T","C",'A']
a3=["G","T","C"]
a=list(productt(a,repeat=n))
a1=0
for i in range(len(a)):
    a[i]="".join(a[i])
    if forr(a3,a[i]):
        a1+=1
print(a1%((10**9)+7))

3**((n+1)//2)+3**(n//2)

n = int(input())
print((3**((n+1)//2)+3**(n//2))%(10**9+7))

import itertools
a=int(input())
forbiddens =list(itertools.product('GTS',repeat=2))
pr=['AA']
for forbidden in forbiddens:
    pr.append(''.join(forbidden))
ms=(list(itertools.product('AGTS', repeat=a)))
ans=[]
for i in range(len(ms)):
    b=''.join(ms[i])
    for j in range(len(b)-1):
        if b[j]+b[j+1] in pr:
            break
    else:
        ans.append(b)
print(len(ans))