CF1236B Alice and the List of Presents

Alice 最近收到了许多礼物。于是她决定将这些礼物打包进盒子里，送给她的朋友们。 现在有 $n$ 种礼物。每种礼物都是完全相同的（即无法区分同一种礼物中的两个），不同种类的礼物是不同的（即可以区分不同种类的礼物）。每种礼物的数量都非常多，可以认为 Alice 拥有每种礼物的无限多个。 另外，有 $m$ 个盒子。每个盒子都要送给不同的人，因此盒子两两不同（可以认为每个盒子上都写着 $m$ 个朋友的名字）。例如，把第一种礼物放进第一个盒子但不放进第二个盒子，与把第一种礼物放进第二个盒子但不放进第一个盒子是不同的方案。 Alice 打包礼物时需要遵守以下规则： - 每个盒子中，每种礼物最多只能放一个，因此每个盒子只能包含不同种类的礼物（即每个盒子包含 $n$ 种礼物的一个子集，允许盒子为空）； - 每种礼物至少要放进某个盒子里。 现在 Alice 想知道，有多少种不同的打包方式。由于答案可能非常大，请你帮她计算方案数，并对 $10^9+7$ 取模。 具体样例和说明见下方。

第一行包含两个用空格分隔的整数 $n$ 和 $m$，表示礼物的种类数和盒子的数量（$1 \leq n, m \leq 10^9$）。

输出一个整数，表示满足 Alice 规则的打包方案数，对 $10^9+7$ 取模。

在第一个样例中，共有七种打包方式： $\{1\}\{\}\{\}$ $\{\}\{1\}\{\}$ $\{\}\{\}\{1\}$ $\{1\}\{1\}\{\}$ $\{\}\{1\}\{1\}$ $\{1\}\{\}\{1\}$ $\{1\}\{1\}\{1\}$ 在第二个样例中，共有九种打包方式： $\{\}\{1,2\}$ $\{1\}\{2\}$ $\{1\}\{1,2\}$ $\{2\}\{1\}$ $\{2\}\{1,2\}$ $\{1,2\}\{\}$ $\{1,2\}\{1\}$ $\{1,2\}\{2\}$ $\{1,2\}\{1,2\}$ 例如，方案 $\{2\}\{2\}$ 是不合法的，因为第一种礼物必须至少放进一个盒子。 由 ChatGPT 4.1 翻译