public class Euler657 {
    static final long kMod = 1000000007L;

    static long modPow(long base, long exp) {
        long result = 1;
        base %= kMod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                result = (result * base) % kMod;
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return result;
    }

    static long solveCase(int alpha, long n) {
        int[] inv = new int[alpha + 1];
        if (alpha >= 1)
            inv[1] = 1;
        for (int i = 2; i <= alpha; ++i) {
            long term = (kMod / i) * inv[(int) (kMod % i)] % kMod;
            inv[i] = (int) (kMod - term);
        }

        long comb = 1;
        int[] coeff = new int[alpha];
        if (alpha > 0)
            coeff[0] = 1;
        for (int k = 0; k < alpha - 1; ++k) {
            comb = (comb * (alpha - k)) % kMod;
            comb = (comb * inv[k + 1]) % kMod;
            coeff[k + 1] = (int) comb;
        }

        long n1 = (n + 1) % kMod;
        long exp = n + 1;

        long sum = 0;
        for (int k = 0; k < alpha; ++k) {
            long geo = 0;
            if (k == 0) {
                geo = 1;
            } else if (k == 1) {
                geo = n1;
            } else {
                long p = modPow(k, exp);
                long num = (p + kMod - 1) % kMod;
                geo = (num * inv[k - 1]) % kMod;
            }

            long term = (coeff[k] * geo) % kMod;
            boolean positive = (((alpha - k + 1) & 1) == 0);
            if (positive) {
                sum = (sum + term) % kMod;
            } else {
                sum = (sum + kMod - term) % kMod;
            }
        }

        return sum;
    }

    public static String solve() {
        long ans = solveCase(10000000, 1000000000000L);
        return Long.toString(ans);
    }

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