Prefixless Palindromes Write a program or function that takes N, and S and outputs the number of palindromes of length S you can build using an alphabet of size N such that any prefix of size between 2 and S-1 is not a palindrome.

For example if N were 2 and S were 5

The valid palindromes would be

01110
10001


And thus the answer would be 2

This is code-golf so answers will be scored in bytes based on their length with fewer bytes being better.
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!