题解，求关注

还是洛谷原题哈哈哈https://www.luogu.com.cn/problem/P1316

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define int long long
#define mod 1000000007
using namespace std;

int n,m;
ll pw[25],ans;
int fa[25];

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

inline void work(int len){
	for(int s=1;s<(1<<(n-len+1));s++){
		for(int i=1;i<=len;i++) fa[i]=i;
		int a[25],tt=0,mp[25]={0};
		for(int i=1;i<=n;i++)
			if(s&(1<<(i-1))) a[++tt]=i;
		for(int i=1;i<=tt;i++)
			for(int j=1;j<=len;j++) mp[a[i]+j-1]|=(1<<j);
		int ss=0;
		for(int i=1;i<=n;i++){
			int xx[25]={0},mm=0;
			for(int j=1;j<=len;j++)
				if(mp[i]&(1<<j)) xx[++mm]=j;
			for(int j=2;j<=mm;j++){
				int u=Find(xx[1]),v=Find(xx[j]);
				if(u!=v) fa[u]=v;
			}
		}
		for(int i=1;i<=n;i++) ss+=(mp[i]==0);
		for(int i=1;i<=len;i++) ss+=(Find(i)==i);
		ans=(ans+pw[ss]*(tt&1?1:-1)+mod)%mod;
	}
}

inline ll calc(ll x,int k){
	ll tmp=1;
	while(k){
		if(k&1) tmp=tmp*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return tmp;
}

signed main(){
	scanf("%d%d",&n,&m);
	pw[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*m%mod;
	for(int i=1;i<=n;i++) work(i);
	printf("%lld\n",ans*calc(calc(m,n),mod-2)%mod);

	return 0;
}