A special palindrome is a palindrome of size $$$n$$$ which contains at most $$$k$$$ distinct characters such that any prefix of size between $$$2$$$ and $$$n-1$$$ is not a palindrome.
You need to count the number of special palindromes.
For example, abba is a special palindrome with n = 4 and k = 2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.
If n = 3 and k = 3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So the answer will be 6.
A single line comprising two integers and
Print the answer to the modulo $$$10^9+9$$$.
$$$1 \leq n \leq 10^5$$$
$$$1 \leq k \leq 10^5$$$
|Sample Input||Sample Output|
Please help with this problem as I can't find any good tutorial over internet and the code/solution provided is different than from what I thought. I don't even understand how states are defined in this.