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:
import java.util.Arrays;
import java.util.Scanner;

/*

1000000000 5000
642932262

 */
public class e {
	static long m = (long) (1e9 + 7);
	static long[] ps;
	static long[] fact, ifact2;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		fact = new long[k + 1];
		ifact2 = new long[k + 1];
		fact[0] = 1;
		for (int i = 1; i <= k; i++)
			fact[i] = (fact[i - 1] * i) % m;
		ifact2[k] = mi(fact[k]);
		for (int i = k - 1; i >= 0; i--)
			ifact2[i] = (ifact2[i + 1] * (i + 1)) % m;
		ps = new long[k + 1];
		for (int i = 1; i <= k; i++)
			ps[i] = pow(i, k);
		long[] ys = new long[k + 1];
		long p2 = 1;
		long mi2 = mi(2);
		for (int nn = 0; nn <= k; nn++) {
			ys[nn] = (solve(nn) * p2) % m;
			p2 = (p2 * mi2) % m;
		}
		interpolatePre(ys.length);
		System.out.println((interpolate(ys, n) * pow(2, n)) % m);
	}

	static long solve(int n) {
		long y = 0;
		for (int i = 1; i <= n; i++) {
			y = (y + (ifact2[n - i] * ifact2[i] % m) * ps[i]) % m;
		}
		return y * fact[n] % m;
	}
	
	static long[] ifact;
	static void interpolatePre(int n) {
		ifact = new long[n];
		long x = 1;
		for (int i = 1; i < n; i++)
			x = (x * i) % m;
		ifact[n-1] = mi(x);
		for (int i = n-2; i >= 0; i--)
			ifact[i] = (ifact[i + 1] * (i + 1)) % m;
	}
	static long interpolate(long[] ys, long xi) {
		int n = ys.length;
		long[] a = new long[n + 1], b = new long[n + 1];
		a[0] = b[n] = 1;
		for (int i = 1; i <= n; i++)
			a[i] = (a[i - 1] * (xi - i + 1)) % m;
		for (int i = n - 1; i >= 0; i--)
			b[i] = (b[i + 1] * (xi - i)) % m;
		long result = 0;
		for (int i = 0; i < n; i++) {
			long t = (a[i] * b[i + 1] % m) * ys[i] % m;
			t = (t * ifact[i] % m) * ifact[n - 1 - i] % m;
			result += (((n - i) & 1) == 0) ? -t : t;
		}
		return ((result % m) + m) % m;
	}

	static long mi(long x) {
		return pow(x, m - 2);
	}

	static long pow(long x, long exp) {
		if (exp < 0) {
			return pow(mi(x), -exp);
		}
		long ans = 1;
		while (exp > 0) {
			if ((exp & 1) == 1)
				ans = (ans * x) % m;
			x = (x * x) % m;
			exp >>= 1;
		}
		return ans;
	}
}