Решение:

from itertools import product

# Алфавит в верхнем регистре
s = ’АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ’
# Добавляем также алфавит в нижнем регистре
s = s + s.lower()
cnt = 0

# Палиндром - значит последние 3 символа это перевернутые первые 3 символа
# значит можем составить только первую половину и мысленно её продублировать и развернуть
for i in product(s, repeat=3):
    word = ’’.join(i)
    # Нужно пропустить неподходящие слова:
    # **Й -> **ЙЙ** - подходит
    # *Й* -> *Й**Й* - не подходит
    # Й** -> Й****Й - не подходит
    # *ЙЙ -> *ЙЙЙЙ* - подходит
    # Й*Й -> Й*ЙЙ*Й - не подходит
    # ЙЙ* -> ЙЙ**ЙЙ - подходит
    # ЙЙЙ -> ЙЙЙЙЙЙ - подходит
    # Делаем вывод, что не подходят слова с одной Й, у которых она не на последнем месте,
    # а также с двумя Й, которые не стоят рядом (в центре не Й)
    if ’Й’ in word:
        if word.count(’Й’) == 1 and word[-1] != ’Й’ or word.count(’Й’) == 2 and word[1] != ’Й’:
            continue
    cnt += 1

print(cnt)