D题
并查集+组合
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 1000000007
int o[];
int find(int x)
{
int t,r;
t = x;
while(x != o[x])
x = o[x];
while(x != t)
{
r = o[t];
o[t] = x;
t = r;
}
return x;
}
void merge(int x,int y)
{
x = find(x);
y = find(y);
if(x != y)
o[x] = y;
}
int main()
{
int i,j,n,m,k,ans = ;
scanf("%d%d%d",&n,&m,&k);
for(i = ;i <= n;i ++)
o[i] = i;
for(i = ;i <= n;i ++)
{
if(k% == )
{
if(*i < k) continue;
if(i + k/ > n) continue;
for(j = ;j < k/;j ++)
{
merge(i-j,i++j);
}
}
else
{
if(*i- < k) continue;
if(i + k/ > n) continue;
for(j = ;j < k/;j ++)
merge(i--j,i++j);
}
}
for(i = ;i <= n;i ++)
{
if(find(i) == i)
ans ++;
}
int sd = ;
for(i = ;i <= ans;i ++)
sd = ((__int64)sd*m)%MOD;
printf("%d\n",sd);
return ;
}