CF150B Quantity of Strings

如果还有人没注意到：Nvodsk 的这个冬天简直冷到极点！寒冷到让人产生奇怪的想法。例如，假设有长度恰好为 $n$ 的字符串，由大小为 $m$ 的字母表组成。其任意长度为 $k$ 的子串都是回文串。满足条件的字符串有多少个？请你计算这样字符串的数量，并对 $1000000007$（$10^9+7$）取模。注意不要漏掉某些字符串！ 提醒一下：如果一个字符串无论从左到右还是从右到左读取都是一样的，那么它就是回文串。

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

输出一个整数，表示满足条件的字符串数量，对 $1000000007$ 取模。

在第一个样例中，只有一个字符串是合法的："a"（我们把字母表里的唯一字母记作 "a"）。 在第二个样例中（如果我们把字母表里的字母分别记作 "a" 和 "b"），只有以下字符串是合法的："aaaaa" 和 "bbbbb"。 由 ChatGPT 5 翻译