Palindrome Smart

Time limit3sMemory limit128 MB

Summary

Count palindromic strings of length 1 to N built from lowercase letters that use at most K distinct letters, modulo 1234567891.

Level: Medium7 of 10
Topics: Combinatorics, Math, Number theory, String
Solved: No attempts yet

Problem

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.

Input

The first line contains two positive integers N and K.

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

Output

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

Examples4

Example 1
Input
```
44 7
```
Expected output
```
240249781
```
Example 2
Input
```
1 1
```
Expected output
```
26
```
Example 3
Input
```
2 10
```
Expected output
```
52
```
Example 4
Input
```
3 2
```
Expected output
```
728
```