Problem:


問題名 DNA

遺伝子は、A, T, G, C からなる文字列です。
この世界の遺伝子は奇妙なことに、ある構文規則に従うことが知られています。

構文規則は、次のような形で与えられます。

非終端記号1: 記号1_1 記号1_2 ... 記号1_n1
非終端記号2: 記号2_1 記号2_2 ... 記号2_n2
...
非終端記号m: 記号m_1 記号m_2 ... 記号m_nm

記号は非終端記号または終端記号のどちらかです。
非終端記号は小文字文字列で表され、終端記号はA, T, G, Cのうちのいくつかの文字が、"["と"]"に囲まれた文字列で表されます。

構文規則の例は次のようになります。

dna: a a b b
a: [AT]
b: [GC]

"非終端記号i: 記号i_1 記号i_2 ... 記号i_ni" を非終端記号 i のルールと呼び、ルールは、構文規則に現れる各非終端記号に対して、ちょうど 1 つづつ存在します。

文字列 s が非終端記号 i に「マッチする」とは、 s = s1 + s2 + ... + sni となるような s の部分文字列 {sj} が存在し、sj (1 ≤ j ≤ ni)がルール内の記号 j にマッチすることをいいます。

文字列 s が終端記号に「マッチする」とは、文字列が 1 文字からなり、その文字が終端記号を表す文字列に含まれることをいいます。

文字列が構文規則に従うとは、非終端記号 1 にその文字列がマッチすることをいいます。

ルール i は、記号のうちに、非終端記号 j (j ≤ i) を含みません。

構文規則と、4つの整数 Na , Nt, Ng, Nc が与えられます。
構文規則に従い、A をちょうど Na 個、T をちょうど Nt 個、G をちょうど Ng 個、C をちょうど Nc 個含むような遺伝子の総数を 1,000,000,007 で割った余りを求めなさい。

Input

Na Nt Ng Nc
m
非終端記号1: 記号 11 記号 12 ... 記号 1n1
非終端記号2: 記号 21 記号 22 ... 記号 2n2
...
非終端記号 m: 記号 m1 記号 m2 ... 記号 mnm

0 ≤ Na, Nt, Ng, Nc ≤ 50

1 ≤ m ≤ 50

1 ≤ ni ≤ 10

1 ≤  記号を表す文字列の長さ  ≤ 20 (※記号にマッチする文字列の長さではないことに注意)

Output

総数を 1,000,000,007 で割った余り

Sample Input 1

1 0 1 0
3
dna: a b
a: [AT]
b: [GC]

Output for the Sample Input 1

1

"AG"の一つです。

Sample Input 2

1 1 1 2
1
k: [ATG] [ATG] [ATG] [C] [C]

Output for the Sample Input 2

6

"ATGCC", "AGTCC", "TAGCC", "TGACC", "GATCC", "GTACC"の6つです。

Sample Input 3

3 1 1 1
3
inv: at b b b
at: [ATG] b
b: [C]

Output for the Sample Input 3

0



Sample input:
1 0 1 0
3
dna: a b
a: [AT]
b: [GC]


Sample output:
1

Submission status: Wrong Answer

Solution code:
table= {}
DP = [-1]*200
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret
    
Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
print(lis)
if len(lis)==Na+Nt+Ng+Nc:
    print(count(lis,0,Na,Nt,Ng,Nc,0,0,0,0))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret


Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            for t in range(i-a+2):
                for g in range(i-a-t+3):
#                    print(i,a,t,g)
                    if a > Na or t > Nt or g > Ng or i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na or t > Nt or g > Ng or i-a-t-g > Nc:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if a > Na or t+1 > Nt or g > Ng or i-a-t-g > Nc:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if a > Na or t > Nt or g+1 > Ng or i-a-t-g > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if a > Na or t > Nt or g > Ng or i-a-t-g+1 > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007
                    """
    for i in DP:
        for j in i:
            for k in j:
                print(k,' ')
                """
    print(DP[len(lis)][Na][Nt][Ng])
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
DP = [-1]*200
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret
    
Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
#print(lis)
if len(lis)==Na+Nt+Ng+Nc:
    print(count(lis,0,Na,Nt,Ng,Nc,0,0,0,0))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret


Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            for t in range(i-a+2):
                for g in range(i-a-t+3):
#                    print(i,a,t,g)
                    if a > Na or t > Nt or g > Ng or i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na or t > Nt or g > Ng or i-a-t-g > Nc:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if a > Na or t+1 > Nt or g > Ng or i-a-t-g > Nc:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if a > Na or t > Nt or g+1 > Ng or i-a-t-g > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if a > Na or t > Nt or g > Ng or i-a-t-g+1 > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007
                    """
    for i in DP:
        for j in i:
            for k in j:
                print(k,' ')
                """
    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret


Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            for t in range(i-a+2):
                for g in range(i-a-t+3):
#                    print(i,a,t,g)
                    if a > Na or t > Nt or g > Ng or i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if i-a-t-g+1 > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007
                    """
    for i in DP:
        for j in i:
            for k in j:
                print(k,' ')
                """
    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret
"""
def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret
"""

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            for t in range(i-a+2):
                for g in range(i-a-t+3):
#                    print(i,a,t,g)
                    if a > Na or t > Nt or g > Ng or i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if i-a-t-g+1 > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007
                    """
    for i in DP:
        for j in i:
            for k in j:
                print(k,' ')
                """
    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret
"""
def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret
"""

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+2):
                if t > Nt:
                    break
                for g in range(i-a-t+3):
                    if g > Ng:
                        break
#                    print(i,a,t,g)
                    if i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if i-a-t-g+1 > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007
                    """
    for i in DP:
        for j in i:
            for k in j:
                print(k,' ')
                """
    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
#                    print(i,a,t,g)
                    if i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if i-a-t-g+1 > Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007

    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Ng+1)]for j in range(Nt+1)]for k in range(Na+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
#                    print(i,a,t,g)
                    if i-a-t-g > Nc:
                        continue
                    ans = DP[i][a][t][g] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
 #                           print(i,a,t,g)
                            DP[i+1][a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                           # print(i)
                            DP[i+1][a][t+1][g] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            #print(i)
                            DP[i+1][a][t][g+1] += ans
                        elif char == 'C':
                            if i-a-t-g+1> Nc:
                                continue
                            #print(i)
                            DP[i+1][a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007

    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DPC = [[[0 for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    DPN = [[[0 for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    #print(DP[4])
    DPC[0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
#                    print(i,a,t,g)
                    if i-a-t-g > Nc:
                        continue
                    ans = DPC[a][t][g] % 1000000007
#                    print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
  #                          print(i,a,t,g)
                            DPN[a+1][t][g] += ans
  #                          print(DP[i+1][a+1][t][g])
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                           # print(i)
                            DPN[a][t+1][g] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            #print(i)
                            DPN[a][t][g+1] += ans
                        elif char == 'C':
                            if i-a-t-g+1> Nc:
                                continue
                            #print(i)
                            DPN[a][t][g] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007
        DPC = DPN
        DPN = [[[0 for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    print(DPC[Na][Nt][Ng]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Nc+1)] for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    #DPN = [[[0 for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1
#    print(DPC)
    #print(DP)
    for i in range(len(lis)):
        hA=hT=hG=hC=False
        #print(i)
        for char in lis[i]:
            if char == 'A':
                hA = True
            elif char == 'G':
                hG  = True
            elif char == 'T':
                hT = True
            else:
                hC = True
#        print(hA,hT,hG,hC)
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
#                    print(i,a,t,g)
                    c = i-a-t-g
                    if c > Nc:
                        continue
                    ans = DP[a][t][g][c] % 1000000007
#                    print(ans)
                    if hA and a+1 <= Na:
                        DP[a+1][t][g][c] += ans
  #                          print(DP[i+1][a+1][t][g])
                    if hT and t+1 <= Nt:
                           # print(i)
                        DP[a][t+1][g][c] += ans
                    if hG and g+1 <=  Ng:
                            #print(i)
                        DP[a][t][g+1][c] += ans
                    if hC and c+1 <= Nc:
                            #print(i)
                        DP[a][t][g][c+1] += ans
#        print(DPC)
                    #DP[i][a][t][g] = ans % 1000000007
        #DPC = DPN
        #DPN = [[[0 for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    print(DP[Na][Nt][Ng][Nc]%1000000007)
else:
    print(0)