# Playground for https://stackoverflow.com/a/59353025/11458991
 
 
import functools
import itertools
import string
 
 
@functools.lru_cache()
def f(N, K):
	if N == 2:
		return K
	M = (N + 1)//2
	return K**M - sum(K**(M - L) * f(L, K) for L in range(2, M+1))
 
 
def is_palindrome(s):
	return s[:(len(s) + 1)//2] == s[len(s)//2:][::-1]
 
 
def brutal_f(N, K):
	alphabet = string.ascii_lowercase[:K]
	ret = 0
	for t in itertools.product(alphabet, repeat=N):
		s = "".join(t)
		if is_palindrome(s) and not any(is_palindrome(s[:i]) for i in range(2, N)):
			ret += 1
	return ret
 
 
print(all(
		f(N, K) == brutal_f(N, K)
		for N in range(12)
		for K in range(4)
	))
 

IyBQbGF5Z3JvdW5kIGZvciBodHRwczovL3N0YWNrb3ZlcmZsb3cuY29tL2EvNTkzNTMwMjUvMTE0NTg5OTEKCgppbXBvcnQgZnVuY3Rvb2xzCmltcG9ydCBpdGVydG9vbHMKaW1wb3J0IHN0cmluZwoKCkBmdW5jdG9vbHMubHJ1X2NhY2hlKCkKZGVmIGYoTiwgSyk6CglpZiBOID09IDI6CgkJcmV0dXJuIEsKCU0gPSAoTiArIDEpLy8yCglyZXR1cm4gSyoqTSAtIHN1bShLKiooTSAtIEwpICogZihMLCBLKSBmb3IgTCBpbiByYW5nZSgyLCBNKzEpKQoKCmRlZiBpc19wYWxpbmRyb21lKHMpOgoJcmV0dXJuIHNbOihsZW4ocykgKyAxKS8vMl0gPT0gc1tsZW4ocykvLzI6XVs6Oi0xXQoKCmRlZiBicnV0YWxfZihOLCBLKToKCWFscGhhYmV0ID0gc3RyaW5nLmFzY2lpX2xvd2VyY2FzZVs6S10KCXJldCA9IDAKCWZvciB0IGluIGl0ZXJ0b29scy5wcm9kdWN0KGFscGhhYmV0LCByZXBlYXQ9Tik6CgkJcyA9ICIiLmpvaW4odCkKCQlpZiBpc19wYWxpbmRyb21lKHMpIGFuZCBub3QgYW55KGlzX3BhbGluZHJvbWUoc1s6aV0pIGZvciBpIGluIHJhbmdlKDIsIE4pKToKCQkJcmV0ICs9IDEKCXJldHVybiByZXQKCgpwcmludChhbGwoCgkJZihOLCBLKSA9PSBicnV0YWxfZihOLCBLKQoJCWZvciBOIGluIHJhbmdlKDEyKQoJCWZvciBLIGluIHJhbmdlKDQpCgkpKQo=