Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
111 - ZOJ Monthly, October 2011 - H
How Many Sets I

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Give a set S, |S| = n, then how many ordered set group (S1, S2, ..., Sk) satisfies S1 ∩ S2 ∩ ... ∩ Sk = ∅. (Si is a subset of S, (1 <= i <= k))

Input

The input contains multiple cases, each case have 2 integers in one line represent n and k(1 <= k <= n <= 231-1), proceed to the end of the file.

Output

Output the total number mod 1000000007.

Sample Input

1 1
2 2

Sample Output

1
9

Author: QU, Zhe
Submit    Status