#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=tmpx%mod;
x=xx%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",anscalc(calc(m,n),mod-2)%mod);
}
确 定
