The Subset - Olympiads Online Judge | DMOJ

The Subset

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem types

Given the first $N$ ~N~ positive integers, there are $2^N - 1$ ~2^N - 1~ non-empty subsets. Bob wants to choose $M$ ~M~ distinct subsets from them so that each integer in the union of the $M$ ~M~ subsets occurred an even number of times. For example, if $N=3$ ~N=3~ and $M=3$ ~M=3~, there are $7$ ~7~ non-empty subsets. Bob can choose the subsets $\{1\}$ ~\{1\}~, $\{2\}$ ~\{2\}~, and $\{1,2\}$ ~\{1,2\}~, where every integer has an even number of occurences. Can you help Bob to find the number of different ways to choose the $M$ ~M~ subsets? Since the answer is huge, ouptut the answer modulo $10^9+7$ ~10^9+7~.

Input Specification

The first line of input contains two integers $N$ ~N~ and $M$ ~M~ ( $N, M \le 10^6$ ~N, M \le 10^6~).

Output Specification

Output one integer, the number of ways to choose subsets.

Constraints

Subtask	Points	Additional constraints
$1$ ~1~	$20$ ~20~	$N, M \le 5$ ~N, M \le 5~.
$2$ ~2~	$30$ ~30~	$N, M \le 3\,000$ ~N, M \le 3\,000~.
$3$ ~3~	$50$ ~50~	No additional constraints.

Sample Input 1

3 3

Sample Output 1

Explanation

There are $7$ ~7~ ways to choose $3$ ~3~ subsets, listed as following:

$\{1\}$ ~\{1\}~, $\{2\}$ ~\{2\}~, $\{1, 2\}$ ~\{1, 2\}~
$\{1\}$ ~\{1\}~, $\{3\}$ ~\{3\}~, $\{1, 3\}$ ~\{1, 3\}~
$\{2\}$ ~\{2\}~, $\{3\}$ ~\{3\}~, $\{2, 3\}$ ~\{2, 3\}~
$\{1\}$ ~\{1\}~, $\{2, 3\}$ ~\{2, 3\}~, $\{1, 2, 3\}$ ~\{1, 2, 3\}~
$\{2\}$ ~\{2\}~, $\{1, 3\}$ ~\{1, 3\}~, $\{1, 2, 3\}$ ~\{1, 2, 3\}~
$\{3\}$ ~\{3\}~, $\{1, 2\}$ ~\{1, 2\}~, $\{1, 2, 3\}$ ~\{1, 2, 3\}~
$\{1, 2\}$ ~\{1, 2\}~, $\{2, 3\}$ ~\{2, 3\}~, $\{1, 3\}$ ~\{1, 3\}~

Sample Input 2

5 3

Sample Output 2

Comments

There are no comments at the moment.