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.Scanner;

public class Main {
     static int mod = 1000000007;
     static long s[][] = new long[5010][5010];
     public static void main(String[] args) {
         Scanner cin = new Scanner(System.in);
         int n,k;
         n = cin.nextInt();
         k = cin.nextInt();
         solve(n,k);
         cin.close();
    }

    static void solve(int n,int k){
        init(k);
        long ans = 0;
        for(int i = 0;i <= Math.min(n,k);i++){
            ans = (ans + quick_(2,n-i) * cal(n-i+1,n) % mod * s[k][i] )% mod;
        }
        System.out.println(ans);
    }

    static long cal(int a,int b){
         long ans = 1;
         for(int i = a;i <= b;i++){
             ans = ans * i % mod;
         }
         return  ans;
    }

    static long quick_(long a,long b){
         long ans = 1;
         while(b>0){
             if((b&1)==1)ans = ans * a  % mod ;
             a = a * a %  mod;
             b >>= 1;
         }
         return ans;
    }

    static void init(int k){
         s[1][1] = 1;
         for(int i = 2;i <= k;i++){
             for(int j = 1;j <= i;j++){
                 s[i][j] = (s[i-1][j-1] + j * s[i-1][j]) % mod;
             }
         }
    }
}