{}
valid_states = [0, 1, 2]
black_count = {0: 0, 1: 1, 2: 1}
def compatible(state1, state2):
return (state1 & state2) == 0
columns = 13
max_blacks = 11
dp = [[[0] * (max_blacks + 1) for _ in valid_states] for _ in range(columns + 1)]
dp[0][0][0] = 1
for col in range(1, columns + 1):
for prev_state in valid_states:
for used_blacks in range(max_blacks + 1):
ways = dp[col - 1][prev_state][used_blacks]
if ways == 0:
continue
for curr_state in valid_states:
if compatible(prev_state, curr_state):
new_blacks = used_blacks + black_count[curr_state]
if new_blacks <= max_blacks:
dp[col][curr_state][new_blacks] += ways
result = sum(dp[columns][state][max_blacks] for state in valid_states)
print(result)