Prefixless Palindromes
Jelly, 10 bytes

ṗŒḂƤ€Ḋ€Ḅċ1


This is a brute-force search over all ns possible strings.

My results differ from the other answers', but the solutions my answer counts seem to be valid.

Try it online!