public class Euler602 {
    static final int MOD = 1000000007;

    static int modPow(int a, int e) {
        long r = 1;
        long x = a;
        while (e > 0) {
            if ((e & 1) == 1)
                r = (r * x) % MOD;
            x = (x * x) % MOD;
            e >>= 1;
        }
        return (int) r;
    }

    public static String solve() {
        int n = 10000000;
        int k = 4000000;
        int m = k - 1;
        int N = n + 1;
        int JMAX = m + 1;

        int[] inv = new int[JMAX + 2];
        if (JMAX + 1 >= 1)
            inv[1] = 1;
        for (int i = 2; i <= JMAX + 1; i++) {
            inv[i] = MOD - (int) (((long) (MOD / i) * inv[MOD % i]) % MOD);
        }

        int ans = 0;
        long binom = 1;
        for (int j = 0; j <= JMAX; j++) {
            int base = JMAX - j;
            int pown = modPow(base, n);
            long term = (binom * pown) % MOD;
            if ((j & 1) == 1) {
                ans = (int) ((ans - term + MOD) % MOD);
            } else {
                ans = (int) ((ans + term) % MOD);
            }

            if (j == JMAX)
                break;
            binom = (binom * (N - j)) % MOD;
            binom = (binom * inv[j + 1]) % MOD;
        }

        return Integer.toString(ans);
    }

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