#include<cstdio>
int n,m,k,t,i,l,r,f[2010];long long ans=1;
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
int main(){
scanf("%d%d%d",&n,&m,&k);t=n;
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i+k-1<=n;i++)for(l=i,r=i+k-1;l<r;l++,r--)if(F(l)!=F(r))t--,f[f[l]]=f[r];
while(t--)(ans*=m)%=1000000007;
printf("%I64d",ans);
return 0;
}

Claris太神辣
看完Claris的题解还是不会
于是求助了机房的wine大佬
用并查集把回文串内相同的并起来，这样可以知道那些字母是一定一样的
也就是说这些字母的本质相同，而答案就是m^(本质不同的字母个数)

#include <cstdio>
#include <cstring>
#include <iostream>

#define mod 1000000007

using namespace std;

typedef long long ll;

const int Maxn = 5010;

ll m, ans = 1;
int n, k, fa[Maxn];

int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

int main() {
    scanf("%d%lld%d", &n, &m, &k);
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 1; i <= n; ++i) {
        int j = i + k - 1, mid = (i + j) / 2;
        if(j > n) break;
        for(int l = i; l <= mid; ++l) {
            int r1 = find(l), r2 = find(j - (l - i));
            if(r1 != r2) fa[r2] = r1;
        }
    }
    for(int i = 1; i <= n; ++i) if(find(i) == i) (ans *= m) %= mod;
    printf("%lld\n", ans);
    return 0;
}

抢到沙发了，哈哈哈

program p1789;
var i,n,m,k:longint;
a,f:array[0..2000] of longint;
t:array[0..2000] of boolean;
sum:int64;
//
procedure init;
begin
read(n,m,k);
end;
//
function gf(p:longint):longint;
var p1,p2:longint;
begin
p1:=p;
while p<>f[p] do p:=f[p];
while p1<>p do
begin
p2:=f[p1];f[p1]:=p;p1:=p2;
end;
exit(p);
end;
//
procedure main;
var i,j,a1,a2:longint;
begin
for i:=1 to n do f[i]:=i;
for i:=1 to n-k+1 do
for j:=1 to k do
begin
a1:=gf(i+j-1);a2:=gf(i+k-j);
f[a1]:=a2;
end;
for i:=1 to n do t[gf(i)]:=true;
sum:=1;
for i:=1 to n do if t[i] then sum:=(sum*m) mod 1000000007;
write(sum);
end;
begin
init;
main;
end.

构造并查集