public class Euler553 {
    static final int kMod = 1000000007;
    static final int kModMinus1 = kMod - 1;

    static long modPow(long base, long exp, long mod) {
        long res = 1 % mod;
        long cur = base % mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                res = mulMod(res, cur, mod);
            }
            cur = mulMod(cur, cur, mod);
            exp >>= 1;
        }
        return res;
    }

    static long mulMod(long a, long b, long mod) {
        long res = (a * b - (long) ((double) a * b / mod) * mod) % mod;
        if (res < 0)
            res += mod;
        return res;
    }

    static int modInv(int a) {
        return (int) modPow(a, kMod - 2, kMod);
    }

    static int mulModInt(long a, long b) {
        return (int) ((a * b) % kMod);
    }

    static class PolyMul {
        int N;

        PolyMul(int n) {
            this.N = n;
        }

        int[] mul(int[] a, int[] b) {
            int[] c = new int[N + 1];
            for (int i = 0; i <= N; i++) {
                long sum = 0;
                for (int j = 0; j <= i; j++) {
                    sum += (long) a[j] * b[i - j];
                    if ((j & 7) == 7)
                        sum %= kMod;
                }
                c[i] = (int) (sum % kMod);
            }
            return c;
        }
    }

    static int[] polyPow(int[] base, int exp, PolyMul pm) {
        int N = pm.N;
        int[] res = new int[N + 1];
        res[0] = 1;

        while (exp > 0) {
            if ((exp & 1) != 0) {
                boolean isIdentity = true;
                if (res[0] != 1)
                    isIdentity = false;
                for (int i = 1; i <= N; i++) {
                    if (res[i] != 0) {
                        isIdentity = false;
                        break;
                    }
                }
                if (isIdentity) {
                    System.arraycopy(base, 0, res, 0, N + 1);
                } else {
                    res = pm.mul(res, base);
                }
            }
            exp >>= 1;
            if (exp == 0)
                break;
            base = pm.mul(base, base);
        }
        return res;
    }

    static int solveNK(int N, int K) {
        int maxN = Math.max(N, K);

        int[] fact = new int[maxN + 1];
        int[] invfact = new int[maxN + 1];
        int[] invInt = new int[maxN + 1];

        fact[0] = 1;
        for (int i = 1; i <= maxN; ++i)
            fact[i] = mulModInt(fact[i - 1], i);

        invfact[maxN] = modInv(fact[maxN]);
        for (int i = maxN; i >= 1; --i)
            invfact[i - 1] = mulModInt(invfact[i], i);

        if (maxN >= 1)
            invInt[1] = 1;
        for (int i = 2; i <= maxN; ++i) {
            invInt[i] = kMod - (int) (1L * (kMod / i) * invInt[kMod % i] % kMod);
        }

        int[] pow2ModM1 = new int[maxN + 1];
        pow2ModM1[0] = 1;
        for (int r = 1; r <= maxN; ++r) {
            pow2ModM1[r] = (int) (2L * pow2ModM1[r - 1] % kModMinus1);
        }

        int[] T = new int[maxN + 1];
        for (int r = 0; r <= maxN; ++r) {
            int e = pow2ModM1[r] - 1;
            if (e < 0)
                e += kModMinus1;
            long v = modPow(2, e, kMod);
            int val = (int) v - 1;
            if (val < 0)
                val += kMod;
            T[r] = val;
        }

        PolyMul pm = new PolyMul(maxN);

        int[] invfactSeries = new int[maxN + 1];
        int[] Bsign = new int[maxN + 1];
        for (int i = 0; i <= maxN; ++i)
            invfactSeries[i] = invfact[i];

        for (int r = 0; r <= maxN; ++r) {
            long b = 1L * T[r] * invfact[r] % kMod;
            int bb = (int) b;
            if ((r & 1) != 0)
                bb = (bb == 0 ? 0 : kMod - bb);
            Bsign[r] = bb;
        }

        int[] convA = pm.mul(Bsign, invfactSeries);
        int[] Acoef = new int[maxN + 1];
        Acoef[0] = 1;
        for (int n = 1; n <= maxN; ++n) {
            int v = convA[n];
            if ((n & 1) != 0)
                v = (v == 0 ? 0 : kMod - v);
            Acoef[n] = v;
        }

        int[] Gcoef = new int[maxN + 1];
        int[] iG = new int[maxN + 1];
        for (int m = 1; m <= maxN; ++m) {
            long sum = 0;
            for (int i = 1; i < m; ++i) {
                sum += 1L * iG[i] * Acoef[m - i] % kMod;
                if (sum >= kMod)
                    sum -= kMod;
            }
            long corr = sum * invInt[m] % kMod;
            int gm = (int) (Acoef[m] - corr);
            if (gm < 0)
                gm += kMod;
            Gcoef[m] = gm;
            iG[m] = (int) (1L * m * Gcoef[m] % kMod);
        }

        int[] Gpow = polyPow(Gcoef, K, pm);
        int[] S = pm.mul(invfactSeries, Gpow);

        int answer = (int) (1L * fact[N] * S[N] % kMod * invfact[K] % kMod);
        return answer;
    }

    public static String solve() {
        return Integer.toString(solveNK(10000, 10));
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}