Subset Intersection Counting

Given a set with N elements, there are \(2^N\) different subsets (including the empty set). You are required to choose a non‐empty collection of these subsets such that the intersection of all the chosen subsets has exactly \(K\) elements. Compute the number of ways to do this modulo \(10^9+7\).

A mathematical formulation of the answer is given by:

\[ Answer = \binom{N}{K} \sum_{j=0}^{N-K} (-1)^j \binom{N-K}{j} \Bigl(2^{2^{N-K-j}} - 1\Bigr) \pmod{10^9+7}. \]

Note that selections are made from the \(2^N\) available subsets, and at least one subset must be selected.

inputFormat

The input consists of two integers: N and K.

\(N\) is the number of elements in the set, and \(K\) is the required size of the intersection. It is assumed that \(0 \le K \le N\). (Constraints are not explicitly specified.)

outputFormat

Output a single integer representing the number of valid selection methods modulo \(10^9+7\).

sample

1 0

2