public class Euler830 {

    static long powInt(long base, int exp) {
        long res = 1;
        for (int i = 0; i < exp; ++i)
            res *= base;
        return res;
    }

    static long mulMod(long a, long b, long mod) {
        long q = (long) ((double) a * b / mod);
        long r = a * b - q * mod;
        while (r < 0)
            r += mod;
        while (r >= mod)
            r -= mod;
        return r;
    }

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

    static class GCDResult {
        long g;
        long x;
        long y;

        GCDResult(long g, long x, long y) {
            this.g = g;
            this.x = x;
            this.y = y;
        }
    }

    static GCDResult extGcd(long a, long b) {
        if (b == 0) {
            return new GCDResult(a, 1, 0);
        }
        GCDResult res = extGcd(b, a % b);
        long x = res.y;
        long y = res.x - res.y * (a / b);
        return new GCDResult(res.g, x, y);
    }

    static long modInv(long a, long mod) {
        GCDResult res = extGcd(a, mod);
        if (res.g != 1)
            return 0;
        long x = res.x % mod;
        if (x < 0)
            x += mod;
        return x;
    }

    static long computeModPrime(long n, int p) {
        long modP3 = powInt(p, 3);
        if (n == 0)
            return 1 % modP3;

        int maxJ = (int) Math.min(n, 3L * p - 1);
        long modBig = powInt(p, 5);

        long[][] binom = new long[maxJ + 1][maxJ + 1];
        binom[0][0] = 1;
        for (int j = 1; j <= maxJ; ++j) {
            binom[j][0] = 1;
            binom[j][j] = 1;
            for (int i = 1; i < j; ++i) {
                long v = binom[j - 1][i - 1] + binom[j - 1][i];
                if (v >= modBig)
                    v -= modBig;
                binom[j][i] = v;
            }
        }

        long[] powI = new long[maxJ + 1];
        for (int i = 0; i <= maxJ; ++i) {
            powI[i] = modPow(i, n, modBig);
        }

        int[] vpFact = new int[maxJ + 1];
        long[] uFact = new long[maxJ + 1];
        uFact[0] = 1 % modP3;

        for (int j = 1; j <= maxJ; ++j) {
            int temp = j;
            int cnt = 0;
            while (temp % p == 0) {
                temp /= p;
                cnt++;
            }
            vpFact[j] = vpFact[j - 1] + cnt;
            uFact[j] = mulMod(uFact[j - 1], temp % modP3, modP3);
        }

        long inv2 = modInv(2 % modP3, modP3);
        long pow2 = modPow(2, n, modP3);
        long nMod = n % modP3;
        long fall = 1 % modP3;
        long sum = 0;

        for (int j = 1; j <= maxJ; ++j) {
            long factor = (nMod - (j - 1)) % modP3;
            if (factor < 0)
                factor += modP3;
            fall = mulMod(fall, factor, modP3);
            pow2 = mulMod(pow2, inv2, modP3);

            int a = vpFact[j];
            long modExt = modP3;
            for (int t = 0; t < a; ++t)
                modExt *= p;

            long N = 0;
            for (int i = 0; i <= j; ++i) {
                long term = mulMod(binom[j][i], powI[i], modBig);
                if ((j - i) % 2 != 0) {
                    N -= term;
                    if (N < 0)
                        N += modBig;
                } else {
                    N += term;
                    if (N >= modBig)
                        N -= modBig;
                }
            }
            if (modExt != modBig)
                N %= modExt;
            if (N < 0)
                N += modExt;

            long NDiv = N;
            for (int t = 0; t < a; ++t)
                NDiv /= p;

            long invU = modInv(uFact[j], modP3);
            long stirling = mulMod(NDiv % modP3, invU, modP3);

            long term = mulMod(stirling, fall, modP3);
            term = mulMod(term, pow2, modP3);
            sum = (sum + term) % modP3;
        }

        return sum % modP3;
    }

    static long combineCrt(long[] rem, long[] mods) {
        long M = 1;
        for (long m : mods)
            M *= m;
        long result = 0;
        for (int i = 0; i < mods.length; ++i) {
            long Mi = M / mods[i];
            long inv = modInv(Mi % mods[i], mods[i]);
            long term = mulMod(rem[i], Mi, M);
            term = mulMod(term, inv, M);
            result = (result + term) % M;
        }
        return result;
    }

    static long computeModAll(long n) {
        int[] primes = { 83, 89, 97 };
        long[] mods = new long[3];
        long[] rems = new long[3];

        for (int i = 0; i < 3; ++i) {
            mods[i] = powInt(primes[i], 3);
            rems[i] = computeModPrime(n, primes[i]);
        }

        return combineCrt(rems, mods);
    }

    public static String solve() {
        long n = 1000000000000000000L;
        long ans = computeModAll(n);
        return Long.toString(ans);
    }

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