说明

wzf最近对字符串非常感兴趣，一直在寻找字符串的谜题。有一次，他突发奇想想要寻找一种特殊的字符串。现在有m种字符，我们需要用这m种字符构造出一个长度为n的字符串，这个字符串的任意一个长度为k的子串都必须是回文串。由于wzf数学很不好，所以他想请你来帮忙计算可以构造出的字符串的数量有多少。

输入格式

第一行输入一个T
接下来T行每行输入三个整数n,m,k(1<=n,m,k<=100000)。

输出格式

输出字符串数量模1e9+7。

3
1 1 1
5 2 4
7 4 20

1
2
16384

提示

第三个样例因为k>n,所以答案为m的n次方