팰린드롬 똑똑

어떤 책에는 다음 과제가 적혀 있다.

길이가 1 이상 N 이하인 모든 팰린드롬 문자열을 생각하자. 각 문자열은 영어 소문자로만 이루어져야 하며, 한 문자열 안에 등장하는 서로 다른 문자의 수는 K개 이하여야 한다.

N과 K가 주어졌을 때, 조건을 만족하는 팰린드롬 문자열의 개수를 구하라. 팰린드롬은 앞에서 읽어도 뒤에서 읽어도 같은 문자열이다. wow와 abba는 팰린드롬이다.

첫째 줄에 자연수 N과 K가 주어진다.

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

조건을 만족하는 팰린드롬 문자열의 개수를 1234567891로 나눈 나머지를 출력한다.