시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 9 2 2 40.000%

문제

진영이는 워드똑똑을 공부한다. 민승이는 워드똑똑을 공부한다. 종혁이는 워드똑똑을 공부한다. 백준이는 워드똑똑을 공부한다. 하지만, 성경이는 워드똑똑을 공부하지 않는다.

워드똑똑을 공부하지 않는 성경이를 본 진영이는 분노로 휩싸여 교실의 책상을 의자로 부셔버렸다. 그리고 나서 의자를 창 밖으로 던졌다. 이 광경을 본 동호는 자기도 워드똑똑을 공부해야하겠다고 느끼면서, 책을 no24에서 인터넷 주문했다.

하지만, no24는 이름에 걸맞게 책을 잘못 보냈다. 이 책의 이름은 “팰린드롬똑똑 (Palindrome Smart)” 이었다.

이 책의 첫 페이지에는 다음과 같이 써있다.

이 책을 산 모든 사람은 다음과 같은 문제를 풀어야한다. 문자열의 길이가 1보다 크거나 같고, N보다 작거나 같은 팰린드롬 문자열을 모두 쓰라. 모든 문자는 알파벳 소문자이고, 모든 팰린드롬 문자열은 K개 보다 작거나 같은 서로 다른 문자를 가져야 한다. 다음 페이지에는 한 페이지에 하나씩 N과 K가 써 있다.

동호는 그 많은 문자열을 다 쓰느니 차라리 개수만 구하겠다고 하고, 개수를 구하기로 했다. 동호가 부러워진 많은 학생들은 다같이 개수를 구하기로 했다.

N과 K가 주어졌을 때, 위의 조건을 만족하는 팰린드롬 문자열의 개수를 출력하는 프로그램을 작성하시오. 팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 얘기한다. 예) wow, abba

입력

첫째 줄에 N, K이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, K은 26보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 조건에 맞는 팰린드롬의 개수를 1234567891로 나눈 나머지를 출력한다.

예제 입력

44 7

예제 출력

240249781

힌트

출처