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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

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

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    int mod = 1000000007;
    long[][] dp;

    long binpow(long base, long exponent, long mod) {
        long ans = 1;
        while (exponent != 0) {
            if ((exponent & 1) == 1) {
                ans = ans * base;
                ans = ans % mod;
            }
            base = base * base;
            base %= mod;
            exponent >>= 1;
        }
        return ans % mod;
    }

    long f(int diffs, int a, int ab) {
        if (dp[diffs][a] >= 0) return dp[diffs][a];
        int b = ab - a;
        if (diffs == 0) {
            return dp[diffs][a] = binpow(2, b, mod);
        }
        return dp[diffs][a] = ((b != 0 ? b * f(diffs - 1, a + 1, ab) : 0) + (a != 0 ? a * f(diffs - 1, a, ab) : 0)) % mod;
    }

    private void solve(FastReader cin) {
        int n, k;
        n = cin.nextInt();
        k = cin.nextInt();
        dp = new long[k + 1][k + 1];
        for (long[] row : dp)
            Arrays.fill(row, -1);
        System.out.println(f(k, 0, n));
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.solve(new FastReader());
    }
}