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.*;
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
         class pair{
          int l,nxt;long w;pair(int a,long b,int c){l=a;w=b;nxt=c;}
         }
         long rpe(long a,long b,long mod){
          long ans=1;
          while(b!=0){
           if((b&1)==1)ans=(ans*a)%mod;
           a=(a*a)%mod;b>>=1;
          }return ans;
         }
         public void solve(int testNumber, InputReader in, PrintWriter out) {
             /*
             int n=in.nextInt();
             pair dp[]=new pair[n+1];dp[1]=new pair(1,0,-1);
             long last=0;
             while(n-->0){
              int t=in.nextInt();
              long p=in.nextLong(),q=in.nextLong();
              p^=last;q^=last;
              if(t==1){
               
              }else{
               out.println(dp[])
              }
             }
             */
             long n=in.nextLong(),k=in.nextLong(),mod=(long)(1E9)+7;
             long a[][]=new long[(int)k+10][2];
             a[1][0]=1;
             for(int i=1;i<=k;i++){
              for(int j=0;j<k+10;j++)a[j][1]=0;
              for(int j=1;j<k+10;j++)a[j][1]=(a[j-1][0]*((n-j+2+mod)%mod))%mod;
              for(int j=0;j<k+10;j++)a[j][0]=0;
              for(int j=1;j<k+9;j++)a[j][0]=(a[j+1][1]-a[j][1]+mod)%mod;
             }
             long ans=0,m=rpe(2,n,mod),iv=rpe(2,mod-2,mod);
             for(int j=1;j<k+10;j++){
              ans=(ans+(m*a[j][1])%mod)%mod;
              m=(m*iv)%mod;
             }out.print(ans);
         }
    }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}