502012 - 集合计数

【题目描述】集合计数(collect)

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

输入

一行两个整数N和K(1≤N≤1000000,0≤K≤N)。

输出

输出一行为答案。

样例

输入

3 2

输出

6

提示

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

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题