题目描述

斯特林数 $n\brace m$ 是组合数学中一个重要的研究对象。$n\brace m$ 的意义是将 $n$ 个不同的元素，恰好划分成 $m$ 个小组的方案数。譬如 ${3\brace 2}=3$，因为将三个不同的元素分成两组有 $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\leq k\leq m} {(-1)^k{m\choose k}(m-k)^n} $$

输入格式

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

输出格式

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

5 2

15

1000 100

34640565

数据范围

• 对于 $25\%$ 的数据：$n,m\leq 20$；
• 对于 $50\%$ 的数据：$n,m\leq 100$；
• 对于 $75\%$ 的数据：$n,m\leq 10000$；
• 对于 $100\%$ 的数据：$1\leq n\leq 10^9$，$1\leq m\leq 10^{6}$。