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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScan in = new MyScan(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, MyScan in, PrintWriter out) {
            long n = in.nextLong();
            int k = in.nextInt();


            long[][] state = new long[k + 1][k + 2];
            state[0][0] = 1;
            for (int s = 0; s < k; s++) {
                for (int t = 0; t <= Math.min(k, n); t++) {
                    state[s + 1][t] += t * (state[s][t]) % Util.M07;
                    state[s + 1][t + 1] += ((n - t) % Util.M07) * (state[s][t]) % Util.M07;

                    state[s + 1][t] %= Util.M07;
                    state[s + 1][t + 1] %= Util.M07;
                }
//            out.println(Arrays.toString(state[s + 1]));
            }

            long res = 0;
            for (int l = 0; l <= k; l++) {
                res += (state[k][l] * Util.powm(2, n - l)) % Util.M07;
                res %= Util.M07;
            }
            out.println(res);

        }

    }

    static class MyScan {
        BufferedReader br;
        StringTokenizer st;

        MyScan(BufferedReader br) {
            this.br = br;
        }

        public MyScan(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        public void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        public String next() {
            findToken();
            return st.nextToken();
        }

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

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

    }

    static class Util {
        public static final long M07 = 1000_000_007;
        public static final long _m = M07;

        public static long powm(long v, long k) {
            if (k == 0) return 1;
            long t = powm(v, k / 2);
            t *= t;
            t %= _m;
            if (k % 2 == 1) {
                t *= v;
            }
            return t % _m;
        }

    }
}