public class Euler658 {
    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 k, long n) {
        int[] inv = new int[k + 2];
        inv[1] = 1;
        for (int i = 2; i <= k + 1; ++i) {
            long term = (kMod / i) * inv[(int) (kMod % i)] % kMod;
            inv[i] = (int) (kMod - term);
        }

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

        long aNext = k % kMod;
        long cCurr = (k + 1) % kMod;
        int[] coeff = new int[k];

        for (int r = k - 1; r >= 0; --r) {
            long A = 0;
            if (r == k - 1) {
                A = aNext;
            } else {
                boolean positive = (((k + 1 - r) & 1) == 0);
                long signedC = positive ? cCurr : (kMod - cCurr);
                A = ((2 * aNext) % kMod + signedC + kMod - 1) % kMod;
                aNext = A;
            }
            coeff[r] = (int) A;

            if (r > 0) {
                cCurr = (cCurr * (r + 1)) % kMod;
                cCurr = (cCurr * inv[k - r + 1]) % kMod;
            }
        }

        long sum = 0;
        for (int r = 0; r < k; ++r) {
            long g = 0;
            if (r == 0) {
                g = 1;
            } else if (r == 1) {
                g = n1;
            } else {
                long p = modPow(r, exp);
                long num = (p + kMod - 1) % kMod;
                g = (num * inv[r - 1]) % kMod;
            }
            long term = (coeff[r] * g) % kMod;
            sum = (sum + 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());
    }
}