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

시간 제한0.25초메모리 제한512 MB

요약

길이 N이고 값이 M 이하인 수열 중 길이 K인 모든 연속 부분 수열이 회문인 수열의 개수를 10^9+7로 나눈 나머지를 구한다.

난이도: 보통10점 중 6점
유형: 조합론, 수학, 유니온 파인드, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

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

입력

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

출력

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

제한

$1 \le N, M, K \le 2{,}000$

예제5

예제 1
입력
```
1 1 1
```
예상 출력
```
1
```
예제 2
입력
```
5 2 1
```
예상 출력
```
32
```
예제 3
입력
```
5 2 2
```
예상 출력
```
2
```
예제 4
입력
```
5 2 3
```
예상 출력
```
4
```
예제 5
입력
```
5 2 4
```
예상 출력
```
2
```

Loading...