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.*;
import java.io.*;
import java.text.*;
public class T{
    static final long mod = (long)1e9+7;
    static int MAX = (int)1e6+1;
    static FastReader in;
    static long[][] dp;
    static HashMap<Long, Long> map;
    public static void main(String[] args){
        in = new FastReader();
        long n = nl(), k = nl();
        dp = new long[(int)k+1][(int)k+1];
        pn(solve(k,0,n));
    }
    
    static long solve(long a, long b, long c){
        long ans = 0;
        if(dp[(int)a][(int)b]>0)return dp[(int)a][(int)b];
        if(a==0)return modPow(2, c);
        if(c>0)ans+=c*solve(a-1,b+1,c-1);
        if(b>0)ans+=b*solve(a-1,b,c);
        ans%=mod;
        dp[(int)a][(int)b] = ans;
        return ans;
    }
    
    static long modPow(long a, long p){
        long out = 1;
        while(p>0){
            if(p%2==1)out = (out*a)%mod;
            a = (a*a)%mod;
            p>>=1;
        }
        return out;
    }
    
    static long[] la(int n){
        long[] out = new long[n];
        for(int i = 0; i< n; i++)out[i] = nl();
        return out;
    }
    
    static void p(Object o){
        System.out.print(o);
    }
    
    static void pn(Object o){
        System.out.println(o);
    }
    
    static String n(){
        return in.next();
    }
    
    static String nln(){
        return in.nextLine();
    }
    
    static int ni(){
        return Integer.parseInt(in.next());
    }
    
    static long nl(){
            return Long.parseLong(in.next());
    }
    
    static double nd(){
        return Double.parseDouble(in.next());
    }
    
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}