Number of Sequences Related to Palindromes

Time limit0.25sMemory limit512 MB

Summary

Count length-N sequences with values up to M such that every length-K window is a palindrome, modulo 1e9+7.

Level: Medium6 of 10
Topics: Combinatorics, Math, Union-find, Dynamic programming
Solved: No attempts yet

Problem

Given N, M, and K, count the number of sequences A that satisfy the following conditions.

The length of A is N.
A consists of natural numbers less than or equal to M.
Every contiguous subsequence of A of length K is a palindrome.

Input

The first line contains N, M, and K.

Output

Print the number of sequences A modulo $10^9+7$ on the first line.

Constraints

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

Examples5

Example 1
Input
```
1 1 1
```
Expected output
```
1
```
Example 2
Input
```
5 2 1
```
Expected output
```
32
```
Example 3
Input
```
5 2 2
```
Expected output
```
2
```
Example 4
Input
```
5 2 3
```
Expected output
```
4
```
Example 5
Input
```
5 2 4
```
Expected output
```
2
```

Loading...