题目描述

以防有人没注意到：今年 Nvodsk 的冬天冷得出奇！天冷得让人开始冒出一些古怪的念头。比如说：现有长度恰好为 $n$ 的字符串，字符集大小为 $m$，要求它的任何长度为 $k$ 的子串都是回文串。这样的字符串有多少个？你需要求出数量对 $10^9+7$ 取模的结果。小心点，别漏掉一两个字符串！

提醒：回文串是指从左往右读和从右往左读都相同的字符串。

输入格式

唯一一行包含三个整数：$n$、$m$ 和 $k$（$1 \le n, m, k \le 2000$）。

输出格式

输出一个整数——满足条件的字符串个数对 $10^9+7$ 取模的结果。

1 1 1

1

5 2 4

2

说明/提示

第一组样例中，只有一个字符串合法："a"（把字符集里唯一的字母记作 "a"）。

第二组样例中（把字母表记为 "a" 和 "b"），合法的字符串是 "aaaaa" 和 "bbbbb"。