← 返回题目列表

Codeforces · 150/B

B. 字符串数量

中文机器翻译题面 查看原题

以防万一有人错过了:今年冬天恩沃茨克非常冷!天气太冷了,让人产生一些奇怪的想法。例如,假设基于大小为 m 的字母表,长度恰好为 n 的字符串。它的任何长度等于 k ​​的子串都是回文。存在多少个这样的字符串?你的任务是找到它们的数量模 1000000007 (109 + 7)。小心一点,不要错过一两根绳子!

让我们提醒您,如果一个字符串可以从左到右和从右到左以相同的方式读取,那么它就是回文。

输入

第一行也是唯一一行包含三个整数:n、m 和 k (1 ≤ n、m、k ≤ 2000)。

输出

打印单个整数 — 所描述类型的字符串数量以 1000000007 (109 + 7) 为模。

示例

输入 #1

1 1 1

输出 #1

1

输入 #2

5 2 4

输出 #2

2

注意

在第一个示例中,只有一个字符串有效:“a”(让我们将字母表中唯一的字母表示为“a”)。

在第二个示例中(如果我们将字母表字母表示为“a”和“b”),以下字符串有效:“aaaaa”和“bbbbb”。