import java.math.BigInteger;

public class Euler969 {

    static final long MOD = 1_000_000_007L;

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

    static boolean isPrimeSmall(int n) {
        if (n < 2)
            return false;
        for (int d = 2; (long) d * d <= n; ++d) {
            if (n % d == 0)
                return false;
        }
        return true;
    }

    static long sumPowersMod(long n, int k) {
        if (n == 0)
            return 0;

        int d = k + 2;
        long[] y = new long[d];
        for (int i = 1; i < d; ++i) {
            y[i] = (y[i - 1] + modPow(i, k)) % MOD;
        }

        long x = n % MOD;
        if (x < d)
            return y[(int) x];

        long[] fact = new long[d];
        long[] invFact = new long[d];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i < d; ++i) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[d - 1] = modPow(fact[d - 1], MOD - 2);
        for (int i = d - 1; i > 0; --i) {
            invFact[i - 1] = (invFact[i] * i) % MOD;
        }

        long[] prefix = new long[d + 1];
        long[] suffix = new long[d + 1];
        prefix[0] = 1;
        suffix[d] = 1;

        for (int i = 0; i < d; ++i) {
            long term = (x - i) % MOD;
            if (term < 0)
                term += MOD;
            prefix[i + 1] = (prefix[i] * term) % MOD;
        }
        for (int i = d - 1; i >= 0; --i) {
            long term = (x - i) % MOD;
            if (term < 0)
                term += MOD;
            suffix[i] = (suffix[i + 1] * term) % MOD;
        }

        long answer = 0;
        for (int i = 0; i < d; ++i) {
            long numerator = (prefix[i] * suffix[i + 1]) % MOD;
            long denominator = (invFact[i] * invFact[d - 1 - i]) % MOD;
            if (((d - 1 - i) & 1) != 0) {
                denominator = (MOD - denominator) % MOD;
            }

            long add = (y[i] * numerator) % MOD;
            add = (add * denominator) % MOD;
            answer = (answer + add) % MOD;
        }

        return answer;
    }

    static long solvePrefix(long n) {
        if (n == 0)
            return 0;

        long answer = 0;
        BigInteger primorial = BigInteger.ONE;
        long primorialMod = 1;
        long factorialMod = 1;

        for (int m = 0;; ++m) {
            if (m >= 2 && isPrimeSmall(m)) {
                primorial = primorial.multiply(BigInteger.valueOf(m));
                primorialMod = (primorialMod * m) % MOD;
            }

            if (m > 0) {
                factorialMod = (factorialMod * m) % MOD;
            }

            if (m > n)
                break;

            long remaining = n - m;
            if (primorial.compareTo(BigInteger.valueOf(remaining)) > 0) {
                break;
            }

            BigInteger[] divRem = BigInteger.valueOf(remaining).divideAndRemainder(primorial);
            long count = divRem[0].longValue();

            long coefficient = (modPow(primorialMod, m) * modPow(factorialMod, MOD - 2)) % MOD;
            if ((m & 1) != 0) {
                coefficient = (MOD - coefficient) % MOD;
            }

            long powerSum = sumPowersMod(count, m);
            long add = (coefficient * powerSum) % MOD;

            answer = (answer + add) % MOD;
        }

        return answer;
    }

    static BigInteger directS(int n) {
        BigInteger[] factorial = new BigInteger[n + 1];
        factorial[0] = BigInteger.ONE;
        for (int i = 1; i <= n; ++i) {
            factorial[i] = factorial[i - 1].multiply(BigInteger.valueOf(i));
        }

        BigInteger total = BigInteger.ZERO;
        for (int t = 1; t <= n; ++t) {
            int m = n - t;
            BigInteger numerator = BigInteger.ONE;
            for (int i = 0; i < m; ++i) {
                numerator = numerator.multiply(BigInteger.valueOf(t));
            }
            if ((m & 1) != 0) {
                numerator = numerator.negate();
            }

            BigInteger denominator = factorial[m];
            if (numerator.remainder(denominator).equals(BigInteger.ZERO)) {
                total = total.add(numerator.divide(denominator));
            }
        }

        return total;
    }

    static long bigIntMod(BigInteger value) {
        BigInteger residue = value.remainder(BigInteger.valueOf(MOD));
        if (residue.compareTo(BigInteger.ZERO) < 0) {
            residue = residue.add(BigInteger.valueOf(MOD));
        }
        return residue.longValue();
    }

    public static String solve() {
        long target = 1_000_000_000_000_000_000L;
        return Long.toString(solvePrefix(target));
    }

    public static void main(String[] args) {
        if (!directS(1).equals(BigInteger.ONE)) {
            System.out.println("Validation failed");
            return;
        }
        if (!directS(3).equals(BigInteger.valueOf(-1))) {
            System.out.println("Validation failed");
            return;
        }

        BigInteger prefix = BigInteger.ZERO;
        for (int n = 1; n <= 10; ++n) {
            prefix = prefix.add(directS(n));
        }
        if (!prefix.equals(BigInteger.valueOf(43))) {
            System.out.println("Validation failed");
            return;
        }
        if (solvePrefix(10) != 43) {
            System.out.println("Validation failed");
            return;
        }

        for (int limit : new int[] { 20, 30, 40 }) {
            BigInteger directPrefix = BigInteger.ZERO;
            for (int n = 1; n <= limit; ++n) {
                directPrefix = directPrefix.add(directS(n));
            }

            long fast = solvePrefix(limit);
            long slow = bigIntMod(directPrefix);
            if (fast != slow) {
                System.out.println("Validation failed for N=" + limit + ": fast=" + fast + ", slow=" + slow);
                return;
            }
        }

        System.out.println(solve());
    }
}