Palindrome Smart

A certain book gives the following task.

Consider every palindrome string whose length is at least 1 and at most N. Each string must consist only of lowercase English letters, and each string may contain at most K distinct letters.

Given N and K, compute how many palindrome strings satisfy these conditions. A palindrome reads the same from left to right and from right to left; strings such as wow and abba are palindromes.

The first line contains two positive integers N and K.

• 1 <= N <= 1,000,000,000
• 1 <= K <= 26

Print the number of palindrome strings satisfying the conditions, modulo 1234567891.