#P2839. 集合计数

    ID: 1945 传统题 1000ms 512MiB 尝试: 1071 已通过: 386 难度: 5 上传者: 标签>CF1800普及+/提高-双射计数容斥原理阶乘逆元预处理费马小定理快速幂二项式反演

集合计数

题目描述

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

输入格式

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

输出格式

一行为答案。

3 2
6

样例说明

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

数据规模与约定

对于100%100\%的数据,1≤N≤1000000,0≤K≤N1\le N\le1000000,0\le K\le N。