TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4487
  • 题目
  • P4487集合计数
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 时限1s,空间限制128m
    问题描述

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

    输入格式

    一行两个整数N,K

    输出格式

    一行为答案。

    样例输入 1

    3 2

    样例输出 1

    6

    样例输入 2

    10 3

    样例输出 2

    430206671

    提示

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

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