import java.util.*;

public class Euler330 {
    static final long DEFAULT_N = 1000000000L;
    static final int MODULUS = 77777777;
    static final int[] PRIME_FACTORS = { 7, 11, 73, 101, 137 };

    static int normalizeMod(long x, int mod) {
        long r = x % mod;
        return (int) (r < 0 ? r + mod : r);
    }

    static int powMod(int base, int exp, int mod) {
        long result = 1;
        long b = normalizeMod(base, mod);
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * b) % mod;
            }
            b = (b * b) % mod;
            exp >>= 1;
        }
        return (int) result;
    }

    static int inverseModPrime(int a, int p) {
        return powMod(a, p - 2, p);
    }

    static int factorialModSmall(long n, int p) {
        int f = 1 % p;
        for (long i = 1; i <= n; i++) {
            f = (int) ((f * (i % p)) % p);
        }
        return f;
    }

    static int[] computeAModPrime(int p, long maxN) {
        int sz = (int) maxN;
        int[] values = new int[sz + 1];
        int[] comb = new int[sz + 1];
        comb[0] = 1;

        int fact = 1 % p;

        for (int n = 0; n <= sz; n++) {
            if (n > 0) {
                comb[n] = 1;
                for (int k = n - 1; k >= 1; k--) {
                    comb[k] += comb[k - 1];
                    if (comb[k] >= p)
                        comb[k] -= p;
                }

                if (n < p) {
                    fact = (int) (((long) fact * n) % p);
                } else {
                    fact = 0;
                }
            }

            long current = fact;
            for (int k = 0; k < n; k++) {
                current += (long) comb[k] * values[k];
                current %= p;
            }

            values[n] = (int) current;
        }

        return values;
    }

    static long reducedIndexForPrime(long n, int p) {
        if (n < p)
            return n;
        long period = (long) p * (p - 1);
        return p + ((n - p) % period);
    }

    static int solveModPrime(int p, long n) {
        long index = reducedIndexForPrime(n, p);
        int[] A = computeAModPrime(p, index);

        int nFactorialMod = (n >= p) ? 0 : factorialModSmall(n, p);
        return normalizeMod((long) nFactorialMod - A[(int) index], p);
    }

    static int crtCombine(int[] residues, int[] moduli) {
        long x = 0;
        long currentModulus = 1;

        for (int i = 0; i < residues.length; i++) {
            int m = moduli[i];
            int a = residues[i];

            int inv = inverseModPrime((int) (currentModulus % m), m);
            int t = (int) ((normalizeMod(a - x, m) * (long) inv) % m);
            x += currentModulus * t;
            currentModulus *= m;
        }

        return normalizeMod(x, MODULUS);
    }

    public static String solve() {
        int[] residues = new int[PRIME_FACTORS.length];
        for (int i = 0; i < PRIME_FACTORS.length; i++) {
            residues[i] = solveModPrime(PRIME_FACTORS[i], DEFAULT_N);
        }
        return String.valueOf(crtCombine(residues, PRIME_FACTORS));
    }

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