За­ме­тим, что две цен­траль­ные буквы лю­бо­го па­лин­дро­ма чётной длины оди­на­ко­вы, то есть об­ра­зу­ют па­лин­дром длины два. Точно так же три цен­траль­ные буквы па­лин­дро­ма нечётной длины об­ра­зу­ют па­лин­дро­мы длины три. Таким об­ра­зом, от­сут­ствие в слове па­лин­дро­мов рав­но­силь­но от­сут­ствию па­лин­дро­мов длины 2 и 3. Это, в свою оче­редь, рав­но­силь­но тому, что любые три под­ряд иду­щие буквы в слове раз­лич­ны.

Пер­вая буква в слове вы­би­ра­ет­ся k спо­со­ба­ми, для сле­ду­ю­щей остаётся k − 1 спо­соб. Каж­дая из по­сле­ду­ю­щих букв не может сов­па­дать с двумя преды­ду­щи­ми, по­это­му для неё остаётся k − 2 спо­со­бов. Все эти числа надо пе­ре­мно­жить, по­это­му мы по­лу­ча­ем фор­му­лу

Ответ: 393600.