P10596 BZOJ2839 Set Counting

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or the problem setter who authorized the problem for BZOJ. If you are the copyright owner and believe that we have infringed your rights, please contact us.

A set with $N$ elements has $2^N$ different subsets (including the empty set). Now, we want to choose some subsets from these $2^N$ subsets (at least one subset), such that the number of elements in their intersection is $K$. Find the number of ways to choose them. Output the answer modulo $10^9+7$.

One line containing two integers $N, K$.

One line containing one integer, representing the answer.

**Sample Explanation** Suppose the original set is $\{A,B,C\}$. Then the valid selections are: $\{AB,ABC\}$, $\{AC,ABC\}$, $\{BC,ABC\}$, $\{AB\}$, $\{AC\}$, $\{BC\}$. **Constraints** For $100\%$ of the testdata, $1 \leq N \leq 1000000$, $0 \leq K \leq N$. Translated by ChatGPT 5