A special palindrome is a palindrome of size N which contains atmost K distinct characters such that any prefix between the size 2 to 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, K=3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So answer will be 6.
Input format
Two integers N and K
Output format
Answer modulo 10^9+9
Constraints
1<=N,K<=10^9
Sample TC
3 3
Output
6
[advanced_iframe securitykey=”undefined” src=”https://code.kodnest.com/” width=”100%” height=”600″]