题目描述

一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$，求取法的方案数，答案模 $1000000007$（$1000000007$是质数）。

输入格式

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

输出格式

一行为答案。

3 2

6

样例说明

假设原集合为$\{A,B,C\}$，则满足条件的方案为：$\{AB,ABC\},\{AC,ABC\},\{BC,ABC\},\{AB\},\{AC\},\{BC\}$。

数据规模与约定

对于$100\%$的数据，$1\le N\le1000000,0\le K\le N$。