Problem: You have a team of N people. For a particular task, you can pick any non-empty subset of people. The cost of having x people for the task is xk. 

Output the sum of costs over all non-empty subsets of people.

Input

Only line of input contains two integers N (1 ≤ N ≤ 109) representing total number of people and k (1 ≤ k ≤ 5000).

Output

Output the sum of costs for all non empty subsets modulo 109 + 7.

Examples

Input

1 1


Output

1


Input

3 2


Output

24

Note

In the first example, there is only one non-empty subset {1} with cost 11 = 1.

In the second example, there are seven non-empty subsets.

- {1} with cost 12 = 1

- {2} with cost 12 = 1

- {1, 2} with cost 22 = 4

- {3} with cost 12 = 1

- {1, 3} with cost 22 = 4

- {2, 3} with cost 22 = 4

- {1, 2, 3} with cost 32 = 9

The total cost is 1 + 1 + 4 + 1 + 4 + 4 + 9 = 24.

Solution (in JAVA):

Solution:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF932E {
	static final int MD = 1000000007;
	static long power(int a, int k) {
		if (k == 0)
			return 1;
		long p = power(a, k / 2);
		p = p * p % MD;
		if (k % 2 == 1)
			p = p * a % MD;
		return p;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] dp = new int[k + 1];
		dp[0] = 1;
		for (int h = 0; h < k; h++) {
			for (int j = k; j > 0; j--)
				dp[j] = (int) (((long) j * dp[j] + (long) (n - j + 1) * dp[j - 1]) % MD);
			dp[0] = 0;
		}
		long ans = 0;
		long p = n < k ? 1 : power(2, n - k);
		for (int j = n < k ? n : k; j >= 1; j--) {
			ans = (ans + dp[j] * p) % MD;
			p = p * 2 % MD;
		}
		System.out.println(ans);
	}
}