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.*;
public class Main {
	static int mod=1000000007;
	static int n,K;
	static int[] p2=new int[5123];
	static int[][] dp=new int[5123][5123];
	static int ksm(int x,int n) {
		int ret=1;
		while (n>0) {
			if ((n&1)==1) ret=(int)(1L*ret*x%mod);
			n>>=1;
			x=(int)(1L*x*x%mod);
		}
		return ret;
	}
	static int DP(int a,int b) {
		if (a==0) return p2[b];
		if (dp[a][b]>0) return dp[a][b];
		int ret=0,c=n-b;
		if (b>0) ret=(ret+(int)(1L*b*DP(a-1,b)%mod))%mod;
		if (c>0) ret=(ret+(int)(1L*c*DP(a-1,b+1)%mod))%mod;
		return dp[a][b]=ret;
	}
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		n=in.nextInt();
		K=in.nextInt();
		p2[0]=ksm(2,n);
		for (int i=1;i<=K;++i) p2[i]=(int)(500000004L*p2[i-1]%mod);
		System.out.println(DP(K,0));
	}
}