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.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.util.Map.Entry;

	
public class Main
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private PrintWriter pw;
		private long mod = 1000000000 + 7;
		
		private StringBuilder ans_sb;
		private int block;
		private double ans = 0;
		private void soln()
		{
			/*String a = nextLine();
			StringBuilder sb = new StringBuilder(a);
			pw.println(a+sb.reverse().toString());*/
			/*int q = nextInt();
			int[][] arr = new int[1000001][10];
			int[] arrr = new int[1000001];
			for(int i=1;i<=1000000;i++) {
				if(i<10) {
					arr[i][i] = 1;
					arrr[i] = i;
				}
				else {
					int fi = 1;
					int x = i;
					while(x != 0) {
						int d = x%10;
						if(d != 0)
							fi *= d;
						x /= 10;
					}
					arr[i][arrr[fi]] = 1;
					arrr[i] = arrr[fi];
				}
				for(int j=1;j<=9;j++)
					arr[i][j] += arr[i-1][j];
			}
			while(q-- > 0) {
				int l = nextInt();
				int r = nextInt();
				int k = nextInt();
				pw.println(arr[r][k] - arr[l-1][k]);
			}*/
			/*int n = nextInt();
			int a = nextInt();
			int b = nextInt();
			int cnt1 = 0;
			int cnt2 = -1;
			for(cnt1 = 0; cnt1 <= n; cnt1++) {
				int x = cnt1*a;
				int y = n - x;
				if(y<0)
					break;
				else if(y%b == 0) {
					cnt2 = y/b;
					break;
				}
			}
		//	debug(cnt1);
		//	debug(cnt2);
			if(cnt2 == -1)
				pw.println(-1);
			else {
				int i = 2;
				int prev = 1;
				while(cnt1-- > 0) {
					int aa = a - 1;
					while(aa-- > 0) {
						pw.print(i+" ");
						i++;
					}
					pw.print(prev+" ");
					prev = i++;
				}
				while(cnt2-- > 0) {
					int aa = b - 1;
					while(aa-- > 0) {
						pw.print(i+" ");
						i++;
					}
					pw.print(prev+" ");
					prev = i++;
				}
			}*/
			int n = nextInt();
			int k = nextInt();
			long[][] dp = new long[k+1][k+1];
			for(int i=0;i<=k;i++)
				for(int j=0;j<=k;j++)
					dp[i][j] = -1;
			for(int i=0;i<=k;i++) {
				dp[i][k] = pow(2,n-i,mod);
			}
			pw.println(recur(n,0,0,dp));
	//		debug(dp);
		}
		public long recur(int n, int k1, int k2, long[][] dp) {
			if(dp[k1][k2] == -1) {
				dp[k1][k2] = (recur(n, k1, k2+1, dp) - recur(n, k1+1, k2+1, dp) + mod)%mod;
				dp[k1][k2] = (dp[k1][k2] * (n-k1))%mod;
			}
//			System.out.println((n-k1)+" "+k2+" "+dp[k1][k2]);
			return dp[k1][k2];
		}
		private class Bridge{
			private LinkedList<Edge>[] graph;
			private LinkedList<Integer>[] tree;
			private int t;
			private boolean[] isBridge;
			private int[] cno;
			public Bridge(int n, int m) {
				pre(n,m);
			}
			private class Edge{
				int u, v, i;
				public Edge(int a, int b, int c) {
					u = a;
					v = b;
					i = c;
				}
			}
			private void pre(int n, int m){
				graph = new LinkedList[n];
				tree = new LinkedList[n];
				for(int i=0; i<m; i++) {
					int u = nextInt() - 1;
					int v = nextInt() - 1;
					Edge e = new Edge(u, v, i);
					graph[u].add(e);
					graph[v].add(e);
				}
				isBridge = new boolean[m];
				cno = new int[n];
				boolean[] v = new boolean[n];
				int[] arr = new int[n];
				for(int i=0; i<n; i++)
					if(!v[i])
						dfs(i, null, v, arr);
			}
			private int dfs(int u, Edge e, boolean[] v, int[] arr) {
				v[u] = true;
				arr[u] = t++;
				int min = arr[u];
				Iterator<Edge> it = graph[u].listIterator();
				while(it.hasNext()) {
					Edge x = it.next();
					int w = x.u;
					if(x.u == u)
						w = x.v;
					if(!v[w])
						min = Math.min(min, dfs(w, x, v, arr));
					else if(x != e)
						min = Math.min(min, arr[w]);
				}
				if(min == arr[u] && e != null)
					isBridge[e.i] = true;
				return min;
			}
			private void bfs(int u, int cmpNo, Queue<Integer>[] q, boolean[] v) {
				int cur = cmpNo;
				cno[cur] = cmpNo;
				q[cur].add(u);
				v[u] = true;
				while(!q[cur].isEmpty()) {
					int x = q[cur].poll();
					Iterator<Edge> it = graph[x].listIterator();
					while(it.hasNext()) {
						Edge x1 = it.next();
						int w = x1.u;
						if(w == x)
							w = x1.v;
						if(!v[w]) {
							if(isBridge[x1.i]) {
								tree[cur].add(0,cmpNo+1);
								tree[cmpNo+1].add(0, cur);
								bfs(w, cmpNo+1, q, v);
							}else {
								bfs(w, cmpNo, q, v);
							}
						}
					}
				}
			}
		}
		private class Pair implements Comparable<Pair>{
			long s,h,ans;
			public Pair(long a,long b,long c) {
				s = a;
				h = b;
				ans = c;
			}
			@Override
			public int compareTo(Pair arg0)
			{
				long mul1 = this.s * arg0.h;
				long mul2 = this.h * arg0.s;
			//	if(mul1 != mul2)
				if(mul1>mul2)
					return -1;
				else if(mul2 > mul1)
					return 1;
				return 0;
				
			//	return 0;
			}
		}
		private String solveEqn(long a, long b) {
	        long x = 0, y = 1, lastx = 1, lasty = 0, temp;
	        while (b != 0){
	        	long q = a / b;
	        	long r = a % b;
	            a = b;
	            b = r;
	            temp = x;
	            x = lastx - q * x;
	            lastx = temp;
	            temp = y;
	            y = lasty - q * y;
	            lasty = temp;
	        }
	        return lastx+" "+lasty;
		}
		private void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		
		private long pow(long a, long b, long c)
		{
			if (b == 0)
				return 1;
			long p = pow(a, b / 2, c);
			p = (p * p) % c;
			return (b % 2 == 0) ? p : (a * p) % c;
		}
	
		private long gcd(long n, long l)
		{
			if (l == 0)
				return n;
			return gcd(l, n % l);
		}
		public static void main(String[] args) throws Exception
		{
			new Thread(null, new Runnable()
			{
				@Override
				public void run()
				{
					new Main().solve();
				}
			}, "1", 1 << 25).start();
		//	new Main().solve();
		}
		public StringBuilder solve(){
			InputReader(System.in);
			/*try { 
				InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\in.txt"));
			} catch(FileNotFoundException e) {}
			*/
			pw = new PrintWriter(System.out);
			//ans_sb = new StringBuilder();
			soln();
			
			pw.close();
			//System.out.println(ans_sb);
			return ans_sb;
		}
		public void InputReader(InputStream stream1)
		{
			stream = stream1;
		}
	
		private boolean isWhitespace(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	
		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}
	
		private int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	
		private int nextInt()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private long nextLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private String nextToken()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
	
		private String nextLine()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
	
		private int[] nextIntArray(int n)
		{
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextInt();
			}
			return arr;
		}
	
		private long[] nextLongArray(int n)
		{
			long[] arr = new long[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextLong();
			}
			return arr;
		}
	
		private void pArray(int[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private void pArray(long[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}
	
		private char nextChar()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			char c1 = (char) c;
			while (!isSpaceChar(c))
				c = read();
			return c1;
		}
	
		private interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}
	}