import copy

yoko=5
tate=10
kuro=19

#joutai0:黒マスを横nマス(n<yoko)に入れる方法をリストアップ

joutai0 = [[] for i in range(yoko+1)]
joutai0[1].extend([[0],[1]])
temp=[]
for i in range(2,yoko+1):
    for j in range(len(joutai0[i-1])):
        temp=copy.deepcopy(joutai0[i-1][j])
        temp.append(0)
        joutai0[i].append(copy.deepcopy(temp))
        if temp[-2]==0:
            temp[-1]=1
            joutai0[i].append(copy.deepcopy(temp))


#joutai1を作る。連なっている黒マスに同じ番号を振る場合の、すべてのパターン
        
joutai1 = []

def t(original,temp_123,checkichi,shurui):
    if checkichi==yoko:
        #終了。joutai1に書き込む
        joutai1.append(copy.deepcopy(temp_123))
    else:
        if original[checkichi]==1:
            for i in range(1,shurui+2):
                temp_123[checkichi]=i
                if i==shurui+1:
                    shurui+=1
                t(original,temp_123,checkichi+1,shurui)
        else:
            t(original,temp_123,checkichi+1,shurui)
                
for i in range(len(joutai0[yoko])):
    original=copy.deepcopy(joutai0[yoko][i])
    checkichi=1
    shurui=0
    temp_123=[0 for i in range(yoko)]
    t(original,temp_123,0,0)
    
#print(joutai1)
print ("joutai1=",len(joutai1))


#joutai2を作る。壁に接続している黒は1とし、他の黒マスの連なりに番号を振る
joutai2=[]

for i in range(len(joutai1)):
    joutaimax=max(joutai1[i])
    temp=copy.deepcopy(joutai1[i])
    joutai2.append(copy.deepcopy(temp))
    if joutaimax==0:
        continue
    if joutaimax==1:
        for j in range(len(joutai1[i])):
            temp[j]*=2
        joutai2.append(copy.deepcopy(temp))
        continue
    for j in range(len(joutai1[i])):
        if temp[j]>0:
            temp[j]+=1
    joutai2.append(copy.deepcopy(temp))

    for j in range(3,joutaimax+2):
        temp2=copy.deepcopy(temp)
        for k in range(len(joutai1[i])):
            if temp2[k]==j:
                temp2[k]=1
            elif temp2[k]>j:
                temp2[k]-=1
        joutai2.append(copy.deepcopy(temp2))

        
#leftwallの場合、左端の黒マスが2以上になることはないので、そのような要素を削除

i=0
while (i<len(joutai2)):
    if joutai2[i][0]>1:
#        print ("delete",joutai2[i])
        joutai2.pop(i)
        i-=1
    i+=1
        
#パリティの異なるマスが同じ数(0,1を除く)になることはない
i=0
tyouhuku=int(yoko/2)
while (i<len(joutai2)):
    odd=[]
    even=[]
    j=0
    while (j<yoko-1):
        odd.append(joutai2[i][j])
        j+=1
        even.append(joutai2[i][j])
        j+=1
    if yoko%2==0:
        odd.append(joutai2[i][yoko-2])
        even.append(joutai2[i][yoko-1])
    else:
        odd.append(joutai2[i][yoko-1])
    check=0
    for k in range(2,tyouhuku+1):
        if (k in odd)and(k in even):
            check=1
    if check==1:
        joutai2.pop(i)
        i-=1
    i+=1
        
#print (joutai2)
print ("joutai2=",len(joutai2))


matrix_seni=[[0 for i in range(len(joutai2))] for j in range(len(joutai2))]

for i in range(len(joutai2)):
    for j in range(len(joutai0[yoko])):
        #黒マスが縦に並んだらスキップ
        if sum([x*y for (x,y) in zip(joutai2[i],joutai0[yoko][j]) ])>0:
            continue

        temp_above=copy.deepcopy(joutai2[i])
        temp_below=copy.deepcopy(joutai0[yoko][j])
        nogood=0
        #白マス分断が生じたらnogood=1にして、スキップする

        k=0
#k=0（左端）のとき
#leftwallの場合、左端の黒マスが2以上になることはない
        if temp_below[k]>0:
            temp_below[k]=1
            ur=temp_above[k+1]
            if ur==1:
                nogood=1
            if ur>1:
                for l in range (k+1,yoko):
                    if temp_above[l]==ur:
                        temp_above[l]=1
#kが両端でないとき
        shurui=max(temp_above)+1
        #新たに現れた黒マスで、aboveに連ならないものには、aboveに無い番号を振っていく
        for k in range (1,yoko-1):
            if temp_below[k]>0:
                ul=temp_above[k-1]
                ur=temp_above[k+1]
                if (ul>0)and(ur>0):
                    if ul==ur:
                        nogood=1
                    elif (ul==1)or(ur==1):
                        temp_below[k]=1
                        for l in range (0,yoko):
                            if (temp_above[l]==ul)or(temp_above[l]==ur):
                                temp_above[l]=1
                            if (temp_below[l]==ul)or(temp_below[l]==ur):
                                temp_below[l]=1
                    else:
                        #upperleftに統一
                        temp_below[k]=ul
                        for l in range (0,yoko):
                            if temp_above[l]==ur:
                                temp_above[l]=ul
                            if temp_below[l]==ur:
                                temp_below[l]=ul
                elif (ul==0)and(ur==0):
                    shurui+=1
                    temp_below[k]=shurui
                elif ul*ur==0:
                    #ul,urの一方のみ0でないとき、その数を入れる
                    temp_below[k]=ul+ur
            if nogood==1:
                break
        if nogood==1:
            nogood=0
            continue
        
        k=yoko-1
#k=yoko-1(右端)のとき
        if temp_below[k]>0:
            if temp_above[k-1]==0:
                shurui+=1
                temp_below[k]=shurui
            else:
                temp_below[k]=temp_above[k-1]

        #出力する。数字をそろえる
        shurui=1
        for k in range(yoko):
            if temp_below[k]==2 and shurui==0:
                shurui=2
            if temp_below[k]>1:
                if temp_below[k]>shurui:
                    shurui+=1
                    temp=temp_below[k]
                    for l in range(yoko):
                        if temp_below[l]==temp:
                            temp_below[l]=shurui
                        elif temp_below[l]==shurui:
                            temp_below[l]=temp

        #matrix_seniに入力。temp_belowで検索して、該当する位置に1を入れる
        jj=0
        for k in range(len(joutai2)):
            if joutai2[k]==temp_below:
                jj=k
                break
            if k==len(joutai2)-1:
                print ("j",joutai2[i])
                print ("j",temp_above)                
                print ("j",temp_below)
                print ("")
                #この文が表示されてしまう場合、belowがjoutai2の中に存在しない
        matrix_seni[i][jj]=1


dp_shurui=len(joutai2)
print ("start")

matrix_kuro=[]
for k in range(dp_shurui):
    count=0
    for i in range(len(joutai2[k])):
        if joutai2[k][i]>0:
            count+=1
    matrix_kuro.append(count)

                                 
matrix_shoki=[]
for k in range(dp_shurui):
    if max(joutai2[k])<2:
        matrix_shoki.append(1)
    else:
        matrix_shoki.append(0)

matrix_hyouji=[]
for k in range(dp_shurui):
    temp=""
    for i in range(len(joutai2[k])):
        if joutai2[k][i]==0:
            temp+="-"
        elif joutai2[k][i]==1:
            temp+="X"
        else:
            temp+=str(joutai2[k][i])
    matrix_hyouji.append(temp)

#for i in range(dp_shurui):
 #   print ("")
#    print ("a",joutai2[i])
#
#    for j in range(dp_shurui):
#        if matrix_seni[i][j]==1:
#            print ("b",joutai2[j])

#    print(joutai2[k])
#    print (temp)

while(tate<15):
    dp=[[[0 for i in range(dp_shurui+1)]for j in range(kuro+1)]for k in range(tate+1)]
    #現在の行、黒マスの個数、最下列の状態の番号
    
    #1行目
    for joutai_new in range (dp_shurui):
        if matrix_shoki[joutai_new]==1:
            #joutai_newが入るかチェック
            kuro_new=matrix_kuro[joutai_new]
            dp[1][kuro_new][joutai_new]+=1
    
    for tate_old in range(1,tate):
        for joutai_new in range (dp_shurui):
            for joutai_old in range (dp_shurui):
                if matrix_seni[joutai_old][joutai_new]==1:
                #joutai_newが入るかチェック
                    for kuro_old in range (kuro+1):
                        if dp[tate_old][kuro_old][joutai_old]>0:
                            kuro_new=kuro_old+matrix_kuro[joutai_new]
#                            print(tate_old+1,kuro_new,joutai_new)
                            dp[tate_old+1][kuro_new][joutai_new]+=dp[tate_old][kuro_old][joutai_old]
    
    printout=0
    if printout==1:
        #解の一部を表示
        for joutai_new in range(dp_shurui):
            d=dp[tate][kuro][joutai_new]
            if d>0:
                tate_comeback=tate
                kuro_comeback=kuro
                joutai_comeback=joutai_new
                print (matrix_hyouji[joutai_comeback])
                while (tate_comeback>1):
                    tate_comeback-=1
                    kuro_comeback-=matrix_kuro[joutai_comeback]
                    for joutai_old in range(dp_shurui):
                        if (matrix_seni[joutai_old][joutai_comeback]==1)and(dp[tate_comeback][kuro_comeback][joutai_old]>0):
                            print (matrix_hyouji[joutai_old])
                            break
                    joutai_comeback=joutai_old
                print ("")
    
    kuroall=0
    for joutai_new in range(dp_shurui):
        d=dp[tate][kuro][joutai_new]
        kuroall+=d
    if kuroall==0:
        tate-=1
        kuro-=4
    else:
        print (kuro, kuroall)
    tate+=1
    kuro+=3