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.

**Input format**

A single line comprising two integers and

**Output format**

Print the answer to the modulo $$$10^9+9$$$.

**Input Constraints**

$$$1 \leq n \leq 10^5$$$

$$$1 \leq k \leq 10^5$$$

Sample Input | Sample Output |

3 2 | 2 |

4 3 | 6 |

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.

I don't think it's possible to understand the solution by looking at the code, so I'll describe it.

Let $$$dp[n]$$$ be the number of special palindromes of size $$$n$$$.

Let's build $$$dp[n]$$$ knowing $$$dp[1], ... dp[n - 1]$$$ by counting the number of all palindromes and subtracting the number of ones that are not special.

If palindrome is not special it has a special palindrome as its prefix (take the smallest prefix that is a palindrome).

Let's prove it's length is no more than $$$\lceil{\frac{n}{2}}\rceil$$$: let $$$l$$$ be $$$\lfloor{\frac{n}{2}}\rfloor$$$, $$$r$$$ be $$$\lceil{\frac{n}{2}}\rceil$$$ and $$$s$$$ be the palindrome of length $$$> \lceil{\frac{n}{2}}\rceil$$$. Then $$$s[l] = s[r]$$$, $$$s[l - 1] = s[r + 1]$$$, $$$s[l - 2] = s[r + 2]$$$ and so on til the end of the palindrome. So basically we have a palindrome of length at least 2 in the end of $$$s$$$, but we can just mirror it and get a palindrome in the beginning, so $$$s$$$ isn't special.

The number of palindromes of length $$$n$$$ with

fixedspecial palindrome of length $$$i$$$ is $$$k^{\lceil{\frac{n}{2}}\rceil - i}$$$.And the final formula for $$$dp[n]$$$ is $$$k^{\lceil{\frac{n}{2}}\rceil} - \sum_{i=1}^{\lceil{\frac{n}{2}}\rceil} dp[i] \cdot k^{\lceil{\frac{n}{2}}\rceil - i}$$$.

As an exercise you can write the sum for odd and even $$$n$$$ and understand how it is changed between $$$n - 1$$$ and $$$n$$$.

AC code

https://codeforces.com/blog/entry/69941?#comment-545737