又是一道我不会的代码超短的题（
一开始想着用生成函数搞，结果怎么都搞不粗来/ll
首先不妨假设音阶之间存在顺序关系，最终答案除以 (m!) 即可。
本题个人认为一个比较亮的地方在于，每个音阶被奏响次数都是偶数这个条件的处理方式。由于是奇偶性，我们可以发现如果我们钦定了其中 (m-1) 个片段对应的音阶集合，那么第 (m) 个片段中的音阶集合一定已经确定了。我们考虑从这个性质入手。设 (dp_i) 表示有多少个包含 (i) 个片段且符合要求的音阶集合，那么我们考虑随便钦定前 (i-1) 个片段的音阶。方案数 (P(2^n-1,i-1))，但是这样会存在某些情况不合法，不难发现不合法的情况只有可能是以下两类：
- 第 (i) 个片段的音阶集合为空
- 第 (i) 个片段的音阶集合与之前某个片段的音阶集合重复
考虑减去不合法的情况。对于第一种情况显然前 (i-1) 个音阶符合要求，方案数 (f_{i-1})，对于第二种情况，考虑第 (i) 个片段与哪个片段重复，有 (i-1) 种可能，再考虑剩余 (i-2) 个片段中有多少种方案，根据 (f) 的定义可知方案数为 (f_{i-2})，再考虑钦定第 (i) 个音阶的方案，由于不能为空也不能与前面 (i-2) 个片段重复，方案数 (2^n-i+1)，因此
[f_i=P(2^n-1,i-1)-f_{i-1}-f_{i-2}·(i-1)·(2^n-i+1)
]
线性地推即可。
时间复杂度 (mathcal O(m))。
注意模数
int n,m,dp[MAXN+5],inv[MAXN+5];
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int main(){
scanf("%d%d",&n,&m);int tot=qpow(2,n);
for(int i=(inv[0]=inv[1]=1)+1;i<=max(n,m);i++) inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
dp[0]=1;for(int i=1,cur=1;i<=m;i++) dp[i]=(0ll+cur-dp[i-1]-1ll*dp[i-2]*(tot-i+1+MOD)%MOD*(i-1)%MOD+MOD+MOD)%MOD,cur=1ll*cur*(tot-i)%MOD;
// for(int i=1;i<=m;i++) printf("%d
",dp[i]);
int res=dp[m];for(int i=1;i<=m;i++) res=1ll*res*inv[i]%MOD;printf("%d
",res);
return 0;
}