Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3556
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
Contest: ZOJ Monthly, October 2011
Submit    Status