该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

本题不再额外提供样例文件。

问题描述

集合 S 包含 1 ~ n 这 n 个整数，该集合的子集有 $2^n$ 个。从所有子集中任意选出一些集合（至少选一个，不能不选），使得恰好有 m 个元素在所选出的每个集合中都存在。

问：有多少种选法？答案可能很大，你只需要输出其 mod ($10^9+7$) 的值。

输入

一行，包含两个整数 n, m

输出

一个整数，表示答案 mod ($10^9+7$)

样例1输入

3 2

样例1输出

6

样例1解释

样例1中，集合 S = {1, 2, 3}

选法有以下 6 种：

（1） {1, 2}

（2） {1, 3}

（3） {2, 3}

（4） {1, 2}, {1, 2, 3}

（5） {1, 3}, {1, 2, 3}

（6） {2, 3}, {1, 2, 3}

样例2输入

2 0

样例2输出

10

样例2解释

样例2中，集合 S = {1, 2}, 子集有 4 个：∅, {1}, {2}, {1,2}.

选法有以下 10 种：

（1） ∅

（2） ∅, {1}

（3） ∅, {2}

（4） ∅, {1,2}

（5） ∅, {1}, {2}

（6） ∅, {1}, {1,2}

（7） ∅, {2}, {1,2}

（8） ∅, {1}, {2}, {1,2}

（9） {1}, {2}

（10） {1}, {2}, {1,2}

样例3输入

123456 7890

样例3输出

486999976

数据说明

30% 的数据：$1 ≤ n ≤ 10, 0 ≤ m ≤ n$。

70% 的数据：$1 ≤ n ≤ 1000, 0 ≤ m ≤ n$。

100% 的数据：$1 ≤ n ≤ 10^6, 0 ≤ m ≤ n$。