시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.25 초 (언어별 추가 시간 없음) 512 MB 78 34 21 36.207%

문제

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

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

입력

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

출력

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

제한

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

예제 입력 1

1 1 1

예제 출력 1

1

예제 입력 2

5 2 1

예제 출력 2

32

예제 입력 3

5 2 2

예제 출력 3

2

예제 입력 4

5 2 3

예제 출력 4

4
  • [1, 1, 1, 1, 1]
  • [1, 2, 1, 2, 1]
  • [2, 1, 2, 1, 2]
  • [2, 2, 2, 2, 2]

예제 입력 5

5 2 4

예제 출력 5

2
  • [1, 1, 1, 1, 1]
  • [2, 2, 2, 2, 2]

예제 입력 6

5 2 5

예제 출력 6

8

예제 입력 7

1000 1000 1000

예제 출력 7

850431726

출처