Question 5

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

New Report

Close