集合计数

一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集）。

现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$，求取法的方案数，答案对 $10^9+7$ 取模（是质数喔~）。

输入格式

一行两个整数 $N, K$。

输出格式

一行一个整数，为答案。

样例输入

3 2

样例输出

6

样例解释

假设原集合为 $\{A, B, C\}$，则满足条件的方案为

$\{AB,\ ABC\},\quad \{AC,\ ABC\},\quad \{BC,\ ABC\},\quad \{AB\},\quad \{AC\},\quad \{BC\},$

共 $6$ 种。

数据范围

• 对于 $100\%$ 的数据，$1\le N\le 10^6$，$0\le K\le N$。

来源与许可

本题题面与测试数据整理自 BZOJ 2839。

样例 1

输入

3 2

输出

6