Problem p03088 (python)

Fixed submission:
n=int(input())
mod=10**9+7
if n==3:
    print(61)
    exit()
zt=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in zt:
        for k in list('AGCT'):
            tmp.append(j+k)
    zt=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
    ng.add('ACG'+i)
    ng.add('GAC'+i)
    ng.add(i+'ACG')
    ng.add(i+'GAC')
z=[]
for j in zt:
    if not j in ng:
        z.append(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   # if not z[i] in ng:
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            #if not z[k] in ng:
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)

Buggy submission (verdict: Runtime Error):
n=int(input())
mod=10**9+7
if n==3:
    print(61)
    exit()
zt=['A','G','C','T']
for i in range(3):
    tmp=[]
    for j in zt:
        for k in list('AGCT'):
            tmp.append(j+k)
    zt=tmp
ng=set([])
for i in list('AGCT'):
    ng.add('AGC'+i)
    ng.add('AG'+i+'C')
    ng.add('A'+i+'GC')
    ng.add(i+'AGC')
    ng.add('ACG'+i)
    ng.add('GAC'+i)
    ng.add(i+'ACG')
    ng.add(i+'GAC')
z=set([])
for j in zt:
    if not j in ng:
        z.add(j)
zn=len(z)
dp=[[0 for j in range(zn)] for i in range(n-3)]
for i in range(zn):
   # if not z[i] in ng:
    dp[0][i]=1
for i in range(n-4):
    for j in range(zn):
        for k in range(zn):
            #if not z[k] in ng:
            if z[j][1:]==z[k][:3]:
                dp[i+1][k]+=dp[i][j]
                dp[i+1][k]%=mod
print(sum(dp[-1])%mod)

Buggy submission (verdict: Runtime Error):
n=int(input())
mod=10**9+7
if n==3:
    print(61)
if n==4:
    print(230)
l=['A','C','G','T']
dic3=dict(AGC=1,ACG=1,GAC=1)
dic4=dict(AGTC=1,AGGC=1,ATGC=1)
ans=0
z=[]
for a in range(4):
    for b in range(4):
        for c in range(4):            
            for d in range(4):
                f=0
                s=""
                s+=l[a]
                s+=l[b]
                s+=l[c]
                s+=l[d]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f==0:
                    ans+=1
                    z+=[s]
n=n-4

if n>0:
    for i in range(n):
        ans%=mod
        ans*=4
        ans%=mod
        for j in range(len(z)):
            z=[]
            for k in range(4):
                f=0
                s=z[j][1:4]+l[k]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f>0:
                    ans-=1
                    z+=[s]
    print(ans%mod)

Buggy submission (verdict: Runtime Error):
n=int(input())
mod=10**9+7
if n==3:
    print(61)
if n==4:
    print(230)
l=['A','C','G','T']
dic3=dict(AGC=1,ACG=1,GAC=1)
dic4=dict(AGTC=1,AGGC=1,ATGC=1)
ans=0
z=[]
for a in range(4):
    for b in range(4):
        for c in range(4):            
            for d in range(4):
                f=0
                s=""
                s+=l[a]
                s+=l[b]
                s+=l[c]
                s+=l[d]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f==0:
                    ans+=1
                    z+=[s]
n=n-4

if n>0:
    for i in range(n):
        ans*=4
        ans%=mod
        for j in range(len(z)):
            for k in range(4):
                f=0
                s=z[1:4]+l[k]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f>0:
                    ans-=1
    print(ans%mod)

Buggy submission (verdict: Runtime Error):
n=int(input())
if n==3:
    print(61)
if n==4:
    print(230)
l=['A','C','G','T']
dic3=dict(AGC=1,ACG=1,GAC=1)
dic4=dict(AGTC=1,AGGC=1,ATGC=1)
ans=0
z=[]
for a in range(4):
    for b in range(4):
        for c in range(4):            
            for d in range(4):
                f=0
                s=""
                s+=l[a]
                s+=l[b]
                s+=l[c]
                s+=l[d]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f==0:
                    ans+=1
                    z+=[s]
n=n-4

if n>0:
    for i in range(n):
        ans*=4
        for j in range(len(z)):
            for k in range(4):
                f=0
                s=z[1:4]+l[k]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f>0:
                    ans-=1
    print(ans)

Buggy submission (verdict: Runtime Error):
n=int(input())
if n==3:
    print(61)
if n==4:
    print(230)
l=['A','C','G','T']
dic3=dict('AGC'=1,'ACG'=1,'GAC'=1)
dic4=dict('AGTC'=1,'AGGC'=1,'ATGC'=1)
ans=0
z=[]
for a in range(4):
    for b in range(4):
        for c in range(4):            
            for d in range(4):
                f=0
                s=""
                s+=l[a]
                s+=l[b]
                s+=l[c]
                s+=l[d]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f==0:
                    ans+=1
                    z+=[s]
n=n-4

if n>0:
    for i in range(n):
        ans*=4
        for j in range(len(z)):
            for k in range(4):
                f=0
                s=z[1:4]+l[k]
                if s[0:3] in dic3:
                    f+=1
                if s[1:4] in dic3:
                    f+=1
                if s in dic4:
                    f+=1
                if f>0:
                    ans-=1
    print(ans)