17360번 - 팰린드롬과 관련된 수열의 개수

N, M, K가 주어졌을 때, 다음 조건을 만족하는 수열 A의 개수를 세어보자.

• A의 크기는 N이다.
• A는 M보다 작거나 같은 자연수로 이루어져 있다.
• A의 크기가 K인 부분 연속 수열은 모두 팰린드롬이다.

첫째 줄에 N, M, K가 주어진다.

첫째 줄에 수열 A의 개수를 10⁹+7로 나눈 나머지를 출력한다.

• 1 ≤ N, M, K ≤ 2,000