가희와 서울 지하철 3호선_백준27884

ttps://www.acmicpc.net/problem/27884

27884번: 가희와 서울 지하철 3호선

a = [[0 for j in range(2)] for i in range(21)]
n, m = map(int,input().split())
for i in range(n):
    a[i][0] = input()
sum = 0
def na(li,n):
    w = 1
    for i in range(n):
        if li[i][1] == 1:
            w *= 5
        else:
            w*=11
    return w

def sw(x,y,z,cnt,max):
    global n
    global a
    global sum
    if x != 0:
        a[n-x][1] = z
    if (a[n - x][1] == 1 and a[n - 1 - x][1]==-1) or (a[n - x][1] == -1 and a[n - 1 - x][1]==1) :
        cnt += 1
        if cnt > max:
            max = cnt
    else:
        cnt = 1

    if cnt > y:
        cnt -= 1
        return
    if x == 1 and max == y:
        sum += na(a,n)
        return
    elif x == 0:
        return
    
    
    sw(x-1,y,1,cnt,max)
    sw(x-1,y,-1,cnt,max)

if n == 1:
    print(16)
else:
    sw(n,m,1,1,1)
    sw(n,m,-1,1,1)
    print(sum%1000000007)