斯特林数(Stirling Numbers)

题目描述

斯特林数 $\{n\brace m\}$ 是组合数学中一个重要的研究对象。$\{n\brace m\}$ 的意义是将 1 到 n 的 n 个整数，分成 m 个小组的方案数。譬如 $\{3\brace 2\}=3$，因为：

{1}, {2,3} {2}, {1,3} {3}, {1,2}

给定 n 与 m，求 $\{n\brace m\}$。由于可能很大，输出答案模 1,000,000,007 的余数。

提示：

$\{n\brace m\} = \{n-1\brace m-1\} + m \cdot \{n-1\brace m\}$

$\{n\brace m\} = \frac{1}{m!} \sum_{0 \le k < m} (-1)^k \binom{m}{k} (m-k)^n$

输入格式

单独一行：两个正整数 n 与 m。

输出格式

单个自然数：表示方案数模指定数字的余数。

数据范围

• 对于 25% 的数据：n, m ≤ 20
• 对于 50% 的数据：n, m ≤ 100
• 对于 75% 的数据：n, m ≤ 10000
• 对于 100% 的数据：1 ≤ n ≤ 10⁹，1 ≤ m ≤ 10⁶

样例输入 #1

5 2

样例输出 #1

15

样例输入 #2

1000 100

样例输出 #2

34640565

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐。

测试点分布