Problem:
 Score : 400 points    Problem Statement You are given an integer N . Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7 :   The string does not contain characters other than A , C , G and T .  The string does not contain AGC as a substring.  The condition above cannot be violated by swapping two adjacent characters once.       Notes A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T .  For example, the substrings of ATCODER include TCO , AT , CODER , ATCODER and (the empty string), but not AC .      Constraints  3 \leq N \leq 100         Input Input is given from Standard Input in the following format:  N       Output Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7 .        Sample Input 1 3      Sample Output 1 61  There are 4^3 = 64 strings of length 3 that do not contain characters other than A , C , G and T . Among them, only AGC , ACG and GAC violate the condition, so the answer is 64 - 3 = 61 .       Sample Input 2 4      Sample Output 2 230       Sample Input 3 100      Sample Output 3 388130742  Be sure to print the number of strings modulo 10^9+7 .

Solution (Python):
def main():
    N = int(input())
    w = "ATCG"
    INF = 10 ** 9 + 7

    table = {}
    for c1 in w:
        for c2 in w:
            for c3 in w:
                table[c1 + c2 + c3] = 1
    NG = ["AGC", "ACG", "GAC"]
    for ng in NG:
        table[ng] = 0

    for i in range(N - 3):
        t = table.copy()
        for c1 in w:
            for c2 in w:
                for c3 in w:
                    s = c1 + c2 + c3
                    if s in NG:
                        continue

                    if c1 == "G" and c3 == "C" or c2 == "G" and c3 == "C":
                        res = 0
                        for c4 in "TCG":
                            ss = c4 + c1 + c2
                            res += table[ss] % INF
                            res %= INF
                        t[s] = res
                        continue
                    res = 0
                    for c4 in w:
                        ss = c4 + c1 + c2
                        res += table[ss] % INF
                        res %= INF
                    t[s] = res
        table = t

    res = 0
    for v in table.values():
        res += v % INF
        res %= INF
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())

D = [[0 for j in range(64)] for i in range(N-2)]

for i in range(64):
    if i%4==0 and (i//4)%4==1 and  (i//16)%4==2:
        D[0][i]=0
    elif i%4==0 and (i//4)%4==2 and  (i//16)%4==1:
        D[0][i]=0
    elif i%4==1 and (i//4)%4==0 and  (i//16)%4==2:
        D[0][i]=0
    else:
        D[0][i]=1
for i in range(N-3):
    for j in range(64):
        for k in range(4):
            if (j//4)%4==0 and (j//16)%4==1 and  k==2:
                add = 0
            elif (j//4)%4==0 and (j//16)%4==2 and  k==1:
                add = 0
            elif (j//4)%4==1 and (j//16)%4==0 and  k==2:
                add = 0
            elif j%4==0 and (j//4)%4==1 and  k==2:
                add = 0
            elif j%4==0 and (j//16)%4==1 and  k==2:
                add = 0
            else:
                new_index=(j//4)%4+((j//16)%4)*4 + k*16
                D[i+1][new_index]=(D[i+1][new_index]+D[i][j])%(10**9+7)
                
                
print(sum(D[N-3])%(10**9+7))

Solution (Python):
from collections import defaultdict
MOD=10**9+7
def swaps(s):
    for i in xrange(1, len(s)):
        yield s[:i-1]+s[i]+s[i-1]+s[i+1:]

n=int(raw_input())
cur={'':1}
for i in xrange(1, n+1):
    new = defaultdict(int)
    for k, v in cur.iteritems():
        for c in 'ACGT':
            k_ = (k+c)[-5:]
            if 'AGC' in k_ or any('AGC' in s for s in swaps(k_)): continue
            new[k_] = (new[k_]+v)%MOD
    
    cur = new

total=0
for v in cur.itervalues():
    total = (total+v)%MOD
print(total)

Solution (Python):
N = int(input())
AAA, AAG, AAC, AAT, AGA, AGG, AGC, AGT, ACA, ACG, ACC, ACT, ATA, ATG, ATC, ATT, GAA, GAG, GAC, GAT, GGA, GGG, GGC, GGT, GCA, GCG, GCC, GCT, GTA, GTG, GTC, GTT, CAA, CAG, CAC, CAT, CGA, CGG, CGC, CGT, CCA, CCG, CCC, CCT, CTA, CTG, CTC, CTT, TAA, TAG, TAC, TAT, TGA, TGG, TGC, TGT, TCA, TCG, TCC, TCT, TTA, TTG, TTC, TTT = 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
for i in range(N-3):
    AAA, AAG, AAC, AAT, AGA, AGG, AGC, AGT, ACA, ACG, ACC, ACT, ATA, ATG, ATC, ATT, GAA, GAG, GAC, GAT, GGA, GGG, GGC, GGT, GCA, GCG, GCC, GCT, GTA, GTG, GTC, GTT, CAA, CAG, CAC, CAT, CGA, CGG, CGC, CGT, CCA, CCG, CCC, CCT, CTA, CTG, CTC, CTT, TAA, TAG, TAC, TAT, TGA, TGG, TGC, TGT, TCA, TCG, TCC, TCT, TTA, TTG, TTC, TTT = AAA + GAA + CAA + TAA, AAA + GAA + CAA + TAA, AAA + GAA + CAA + TAA, AAA + GAA + CAA + TAA, AAG + GAG + CAG + TAG, AAG + GAG + CAG + TAG, 0, AAG + GAG + CAG + TAG, AAC + GAC + CAC + TAC, 0, AAC + GAC + CAC + TAC, AAC + GAC + CAC + TAC, AAT + GAT + CAT + TAT, AAT + GAT + CAT + TAT, AAT + GAT + CAT + TAT, AAT + GAT + CAT + TAT, AGA + GGA + CGA + TGA, AGA + GGA + CGA + TGA, 0, AGA + GGA + CGA + TGA, AGG + GGG + CGG + TGG, AGG + GGG + CGG + TGG, GGG + CGG + TGG, AGG + GGG + CGG + TGG, AGC + GGC + CGC + TGC, AGC + GGC + CGC + TGC, GGC + CGC + TGC, AGC + GGC + CGC + TGC, AGT + GGT + CGT + TGT, AGT + GGT + CGT + TGT, GGT + CGT + TGT, AGT + GGT + CGT + TGT, ACA + GCA + CCA + TCA, ACA + GCA + CCA + TCA, ACA + GCA + CCA + TCA, ACA + GCA + CCA + TCA, ACG + GCG + CCG + TCG, ACG + GCG + CCG + TCG, GCG + CCG + TCG, ACG + GCG + CCG + TCG, ACC + GCC + CCC + TCC, ACC + GCC + CCC + TCC, ACC + GCC + CCC + TCC, ACC + GCC + CCC + TCC, ACT + GCT + CCT + TCT, ACT + GCT + CCT + TCT, ACT + GCT + CCT + TCT, ACT + GCT + CCT + TCT, ATA + GTA + CTA + TTA, ATA + GTA + CTA + TTA, ATA + GTA + CTA + TTA, ATA + GTA + CTA + TTA, ATG + GTG + CTG + TTG, ATG + GTG + CTG + TTG, GTG + CTG + TTG, ATG + GTG + CTG + TTG, ATC + GTC + CTC + TTC, ATC + GTC + CTC + TTC, ATC + GTC + CTC + TTC, ATC + GTC + CTC + TTC, ATT + GTT + CTT + TTT, ATT + GTT + CTT + TTT, ATT + GTT + CTT + TTT, ATT + GTT + CTT + TTT
print((AAA + AAG + AAC + AAT + AGA + AGG + AGC + AGT + ACA + ACG + ACC + ACT + ATA + ATG + ATC + ATT + GAA + GAG + GAC + GAT + GGA + GGG + GGC + GGT + GCA + GCG + GCC + GCT + GTA + GTG + GTC + GTT + CAA + CAG + CAC + CAT + CGA + CGG + CGC + CGT + CCA + CCG + CCC + CCT + CTA + CTG + CTC + CTT + TAA + TAG + TAC + TAT + TGA + TGG + TGC + TGT + TCA + TCG + TCC + TCT + TTA + TTG + TTC + TTT)%(10**9+7))

Solution (Python):
MOD = 10**9 + 7
N = int(input())

ATCG = "ATCG"

memo = {}
def dfs(i, last):
    if i == N:
        return 1
    key = (i, last)
    if key in memo:
        return memo[key]
    p = None
    l2 = last[-2:]
    if l2 == "AC":
        p = "G"
    elif l2 == "AG":
        p = "C"
    elif l2 == "GA":
        p = "C"
    elif last == "AGG" or last == "ATG" or last == "AGT":
        p = "C"
    res = 0
    for c in ATCG:
        if c == p:
            continue
        res += dfs(i+1, last[1:] + c)
    memo[key] = res = res % MOD
    return res
print(dfs(0, "***"))

Solution (Python):
N=int(input())
mod=10**9+7
acgt=['A','C','G','T']
bef=dict()
from collections import defaultdict
banc=['AGC','GAC','ACG']
for x in acgt:
    for y in acgt:
        for z in acgt:
            if x+y+z not in banc:
                bef[x+y+z]=1
ban=[]
for w in acgt:
    for v in banc:
        ban.append(w+v)
    ban.append('A'+w+'GC')
    ban.append('AG'+w+'C')
for i in range(3,N):
    befc=bef.copy()
    bef=defaultdict(int)
    for b in befc.keys():
        for nex in acgt:
            if b+nex not in ban:
                bef[b[1:]+nex]=(bef[b[1:]+nex]+befc[b])%mod
ans=0
for cnt in bef.values():
    ans=(ans+cnt)%mod
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
n = int(input())
dp = [[[1] * 4 for _ in [0] * 4] for _ in [0] * 4]
dp[0][2][1] = 0
dp[0][1][2] = 0
dp[2][0][1] = 0
for _ in range(n - 3):
    ndp = [[[0] * 4 for _ in [0] * 4] for _ in [0] * 4]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    if (i, k, l) == (0, 2, 1) or (i, j, l) == (0, 2, 1):
                        pass
                    else:
                        ndp[j][k][l] += dp[i][j][k]
    dp = ndp
    dp[0][2][1] = 0
    dp[0][1][2] = 0
    dp[2][0][1] = 0
    for j in range(4):
        for k in range(4):
            for l in range(4):
                dp[j][k][l] %= MOD
print(sum(z for x in dp for y in x for z in y) % MOD)

Solution (Python):
from itertools import product

n = int(input())
i = 3
ans = 61
dpm = {
    "".join(k): 1
    for k in product("ACGT", repeat=3)
}
for k in ("AGC", "ACG", "GAC"):
    dpm[k] = 0

MOD = 1000000007

while i < n:
    ndpm = {k: 0 for k in dpm}
    for k in dpm:
        for c in "ACGT":
            ns = k + c
            if ns[-3:] in ("AGC", "ACG", "GAC") or \
                    (ns[0] == "A" and ns[-2:] == "GC") or \
                    (ns[0:2] == "AG" and ns[-1] == "C"):
                continue
            ndpm[ns[-3:]] += dpm[k] % MOD
    dpm = ndpm
    i += 1

print(sum(dpm.values()) % MOD)

Solution (Python):
from collections import deque, defaultdict as ddic
from itertools import combinations, permutations, product
from heapq import heappush, heappop, heapify
import sys
stdout = sys.stdout
rr = lambda: input().strip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))

MOD = 10**9 + 7
memo = {}
banned = {'ACTG', 'TCAG', 'GCAG', 'TACG', 'AACG', 'ACAG', 'GAGC', 'CACG', 'AGC', 'ATCG', 'ACCG', 'CAG', 'GACG', 'CCAG', 'AAGC', 'ACG', 'TAGC'}

def dp(letters, state):
    if state in banned:
        return 0
    if letters == 0:
        return 1
    if (letters, state) in memo:
        return memo[letters, state]
    
    ans = 0
    for c in 'ACGT':
        ans += dp(letters - 1, (state + c)[-4:])
        ans %= MOD
    ans %= MOD
    memo[letters, state] = ans
    return ans

print(dp(rri(), ''))