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 utkarsh {

    InputStream is;
    PrintWriter out;
    
    int N = 5005;
    long mod = (long)1e9 + 7L;
    long fact[], inv[], inv_i[];
    
    void play() {
        fact = new long[N];
        inv = new long[N];
        inv_i = new long[N];
        fact[0] = inv[0] = 1;
        fact[1] = inv[1] = 1;
        inv_i[1] = 1;
        for(int i = 2; i < N; i++) {
            fact[i] = (fact[i-1] * i) % mod;
            inv[i] = modpow(fact[i], mod - 2, mod);
            inv_i[i] = modpow(i, mod - 2, mod);
        }
    }
    
    long nCr(int n, int r) {
        return ((fact[n] * inv[r]) % mod * inv[n-r]) % mod;
    }
    
    long ncr(int n, int r) {
        long ans = 1;
        if(r > (n-r))   r = (n-r);
        for(int i = 1, j = n; i <= r; i++, j--) {
            ans *= (j * inv_i[i] % mod);
            ans %= mod;
        }
        return ans;
    }
    
    void solve(){
        //Enter code here utkarsh
        play();
        int n = ni();
        int k = ni();
        long d[] = new long[N];
        long ans = 0;
        for(int i = 1; i <= k && i <= n; i++) {
            long x = ncr(n, i);
            long y = modpow(2, n-i, mod);
            long z = modpow(i, k, mod);
            for(int j = 1; j < i; j++) {
                long t = d[j] * nCr(i, j) % mod;
                z = (z - t + mod) % mod;
            }
            ans += (x * y % mod) * z % mod;
            ans %= mod;
            d[i] = z;
        }
        out.println(ans);
    }
    
    long modpow(long base, long exp, long modulus) { base %= modulus; long result = 1L; while (exp > 0) { if ((exp & 1)==1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result;
    }
    
    public static void main(String[] args) { new utkarsh().run();
    }
    void run(){ is = System.in; out = new PrintWriter(System.out); solve(); out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte(){ if(ptr >= len){ ptr = 0; try{ len = is.read(input); }catch(IOException e){ throw new InputMismatchException(); } if(len <= 0){ return -1; } } return input[ptr++];
    }
    boolean isSpaceChar(int c){ return !( c >= 33 && c <= 126 ); 
    }
    int skip(){ int b = readByte(); while(b != -1 && isSpaceChar(b)){ b = readByte(); } return b;
    }
    
    char nc(){ return (char)skip();
    }
    String ns(){ int b = skip(); StringBuilder sb = new StringBuilder(); while(!isSpaceChar(b)){ sb.appendCodePoint(b); b=readByte(); } return sb.toString();
    }
    int ni(){ int n = 0,b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } if(b == -1){ return -1; } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
    }
    long nl(){ long n = 0L; int b = readByte(); boolean minus = false; while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')){ b = readByte(); } if(b == '-'){ minus = true; b = readByte(); } while(b >= '0' && b <= '9'){ n = n * 10 + (b - '0'); b = readByte(); } return minus ? -n : n;
    }
}