#!/usr/bin/env python3
# Program pro 31-3-4 (Martin Medvěd Mareš)

# Zadání víceřádkové úlohy

B = 3           # Počet barev
N = 999         # Šířka sálu
K = 3           # Výška sálu
leva = 0        # Barvy stěn
prava = 0
horni = 0
dolni = 2

# Seznam dlaždic
dlazdicky_2d = [    # (levá, pravá, horní, dolní)
    (0,0,0,1),
    (0,1,1,2),
    (1,2,1,2),
    (2,0,1,2),
    (0,0,2,2),
]

# Konverze víceřádkové úlohy na jednořádkovou

import itertools

# Pomocná funkce pro číslování K-tic barev
barvy = {}
def koduj_barvu(Ktice):
    Ktice = tuple(Ktice)
    if Ktice not in barvy:
        barvy[Ktice] = len(barvy)
    return barvy[Ktice]

# Vytváříme dlaždičky
dlazdicky = []
for sl in itertools.product(dlazdicky_2d, repeat=K):
    if sl[0][2] == horni and sl[K-1][3] == dolni and \
           len([ i for i in range(1,K) if sl[i-1][3] != sl[i][2] ]) == 0:
       dlazdicky.append(( koduj_barvu([ sl[i][0] for i in range(K) ]), koduj_barvu([ sl[i][1] for i in range(K) ]) ))

# Barvy stěn
leva = koduj_barvu([leva] * K)
prava = koduj_barvu([prava] * K)
B = len(barvy)

# Vypíšeme přeloženou úlohu
print(barvy)
print(dlazdicky)
print(leva, prava, B, N, K)

# Řešení jednořádkové úlohy

def S1():
    S = []
    for b in range(B):
        S.append(set([ c for (bb,c) in dlazdicky if bb == b ]))
    return S

def kombinuj(Si, Sj):
    S = []
    for b in range(B):
        out = set()
        for c in Si[b]:
            out = out.union(Sj[c])
        S.append(out)
    return S

S = S1()
X = None
n = N
while n > 0:
    if n%2 == 1:
        if X is None:
            X = S
        else:
            X = kombinuj(X, S)
    n = n//2
    S = kombinuj(S, S)

print(prava in X[leva])