Решение:

import itertools

count = 0
for digits in itertools.product(range(8), repeat=5):
    if digits[0] != 0 and digits.count(6) == 1:
        idx = digits.index(6)
        if ((idx == 0) or (digits[idx-1] % 2 == 0)) and ((idx == 4) or (digits[idx+1] % 2 == 0)):
            count += 1

print(count)

Ответ: 2961