题目描述
众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。
他将声音分成 $n$ 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 $1$ 到 $n$ 个音阶构成的和声，即从 $n$ 个音阶中挑选若干个音阶同时演奏出来。
为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。
现在的问题是：小余想知道包含 $m$ 个片段的音乐一共有多少种。
两段音乐 $a$ 和 $b$ 同种当且仅当将 $a$ 的片段重新排列后可以得到 $b$。例如：假设 $a$ 为 $\set{\set{1,2},\set{2,3}}$，$b$ 为 $\set{\set{2,3},\set{1,2}}$，那么 $a$ 与 $b$ 就是同种音乐。
答案对 $10^8+7$ 取模。
输入格式
仅一行两个正整数 $n,m$
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
【数据范围】
- 对于 $20%$ 的数据，$1\le n,m \le 5$；
- 对于 $50%$ 的数据，$1\le n,m \le 3000$；
- 对于 $100%$ 的数据，$1\le n,m \le 10^6$。
【样例解释】
- 音乐为 $\set{\set{1},\set{2},\set{1,2}}$
题解
本题可转化为：在集合 $S = \set{1, 2, \cdots, n}$ 中选出 $m$ 个子集，满足性质：
- 每个子集不为空；
- 任何两个子集不相同；
- 在所有子集中，每个元素出现的总次数为偶数。
定义 $f(i)$ 为逐个选出 $i$ 个子集满足条件的方案数。
由性质 3 可知，确定了前 $i-1$ 个非空子集后，第 $i$ 个子集也确定下来。因此方案数为 $A_{2^n-1}^{i-1}$。
去掉不满足性质 1 的方案数。若最后一个子集为空，则前 $i-1$ 个子集已经满足了所有条件，方案数为 $f(i-1)$。
去电不满足性质 2 的方案数。若第 $j$ 个子集和第 $i$ 个子集相同，则除这两个子集外剩下的 $n-2$ 个子集是一个合法的方案。因此方案数为 $f(i-2) \times (i-1) \times (2^n - 1 - (i - 2))$。
因此有 $$ f(i) = A_{2^n-1}^{i-1} - f(i-1) - f(i-2) \times (i-1) \times (2^n - i + 1) $$ 由于我们的定义“逐个选出”与题目要求的“同种音乐”相冲突，将方案数除以 $m!$ 即可。
