不错的一个并查集的题目= - =应该是套路题吧...
把必须相同的归为一类,然后m^t即是答案,因为每一类都有m种选择.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
const int mod=1e9+7;
int fa[N],vis[N];
int f(int x)
{
    if(x==fa[x]) return x;
    else         return fa[x]=f(fa[x]);
}

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    ll n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i+k-1<=n;i++)
    {
        int len=i+k-1;
        for(int j=0;j<k;j++)
        {
            int x=f(i+j),y=f(len-j);
            if(x!=y) fa[y]=x;
        }
    }ll t=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[f(i)]) t++,vis[f(i)]=1;
    }
    ll ans=qp(m,t);
    printf("%lld\n",ans);
    return 0;
}