Background

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.

Problem Description

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$.

Input Format

One line containing two integers $N, K$.

Output Format

One line containing one integer, representing the answer.

3 2

6

Hint

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