题目描述

现在有一个长度为 $N$ 的字符串，它的字典集为 $M$。也就是说每一位有 $M$ 种不同的字母可以选。

对于这个字符串所有连续的长度为 $K$ 的子串都必须是回文串，请问有多少种不同的方案。

输入格式

一行三个整数 $N,M,K$，$1\le N,M,K\le 2000$。

输出格式

输出一个整数表示答案，对 $10^9+7$ 取模。

1 1 1

1

5 2 4

2