UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2839. 集合计数

统计 下载数据

Description

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

Input

一行两个整数N,K

Output

一行为答案。

Sample Input

3 2

Sample Output

6

Hint

【样例说明】

假设原集合为{A,B,C}

则满足条件的方案为:{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}

【数据说明】

     对于100%的数据,1≤N≤1000000;0≤K≤N;

Source