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.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class team_work
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static long mod=(long)(1e9+7);
	static int[][] dp;
	static int[] fact,inv_fact;
	static int maxn=5005;
	static int n,k;
	
	static int add(long a,long b)
	{
		long ret=a+b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int mul(long a,long b)
	{
		long ret=a*b;
		
		if(ret>=mod)
		{
			ret%=mod;
		}
		
		return (int)ret;
	}
	
	static int pow(long a,long b)
	{
		long x=1,y=a;
		
		while(b>0)
		{	
			if(b%2==1)
			{
				x=mul(x,y);
			}
			
			y=mul(y,y);b=b/2;
		}
		
		return (int)(x%mod);
	}
	
	static void build()
	{
		fact=new int[maxn];inv_fact=new int[maxn];fact[0]=1;

		for(int i=1;i<maxn;i++)
		{
			fact[i]=mul(fact[i-1],i);
		}

		inv_fact[maxn-1]=pow(fact[maxn-1],mod-2);

		for(int i=maxn-2;i>=0;i--)
		{
			inv_fact[i]=mul(inv_fact[i+1],(i+1));
		}
	}
	
	static int C(int n,int r)
	{
		if(n-r<0 || Math.min(n,r)<0)
		{
			return 0;
		}
		
		int val1=fact[n],val2=inv_fact[r],val3=inv_fact[n-r];
		
		int mul=mul(val2,val3);
		
		return mul(val1,mul);
	}
	
	static int solve(int idx,int level)
	{
		// x^a,(1+x)^(n-a)...
		
		if(level==0)
		{
			return pow(2,n-idx);
		}
		
		if(dp[idx][level]!=-1)
		{
			return dp[idx][level];
		}
		
		else
		{
			int ret=add(mul(idx,solve(idx,level-1)),mul(n-idx,solve(idx+1,level-1)));
			
			dp[idx][level]=ret;return ret;
		}
	}
	
    public static void main(String args[]) throws Exception
    {
		n=sc.nextInt();k=sc.nextInt();build();
		
		if(n<=5000)	
		{
			int res=0;
			
			for(int i=1;i<=n;i++)
			{
				int curr=mul(pow(i,k),C(n,i));
				
				res=add(res,curr);
			}
			
			out.println(res);
		}
		
		else
		{
			dp=new int[k+1][k+1];
			
			for(int i=0;i<=k;i++)
			{
				for(int j=0;j<=k;j++)
				{
					dp[i][j]=-1;
				}
			}
			
			out.println(solve(0,k));
		}
		
		out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}