import java.util.Arrays;

public class Euler767 {
    static final long TARGET_MOD = 1000000007L;

    static long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                // To avoid BigInteger, we could use modular multiplication
                // But since mod is ~10^9, base * res can be ~10^18, which fits in signed 64-bit
                // long (up to 9 * 10^18)
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    static long modInverse(long n, long mod) {
        return power(n, mod - 2, mod);
    }

    static class NTTMod {
        long mod;
        long root;

        NTTMod(long mod, long root) {
            this.mod = mod;
            this.root = root;
        }
    }

    static final NTTMod P1 = new NTTMod(998244353L, 3L);
    static final NTTMod P2 = new NTTMod(1004535809L, 3L);
    static final NTTMod P3 = new NTTMod(469762049L, 3L);

    static void ntt(long[] a, boolean invert, NTTMod p) {
        int n = a.length;
        for (int i = 1, j = 0; i < n; i++) {
            int bit = n >> 1;
            for (; (j & bit) != 0; bit >>= 1)
                j ^= bit;
            j ^= bit;
            if (i < j) {
                long temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        for (int len = 2; len <= n; len <<= 1) {
            long wlen = power(p.root, (p.mod - 1) / len, p.mod);
            if (invert)
                wlen = modInverse(wlen, p.mod);
            int half = len / 2;
            for (int i = 0; i < n; i += len) {
                long w = 1;
                for (int j = 0; j < half; j++) {
                    long u = a[i + j];
                    long v = (a[i + j + half] * w) % p.mod;
                    a[i + j] = (u + v < p.mod) ? (u + v) : (u + v - p.mod);
                    a[i + j + half] = (u - v >= 0) ? (u - v) : (u - v + p.mod);
                    w = (w * wlen) % p.mod;
                }
            }
        }

        if (invert) {
            long nInv = modInverse(n, p.mod);
            for (int i = 0; i < n; i++) {
                a[i] = (a[i] * nInv) % p.mod;
            }
        }
    }

    static long[] convolve(long[] a, long[] b, NTTMod p) {
        int n = 1;
        while (n < a.length + b.length)
            n <<= 1;
        long[] fa = Arrays.copyOf(a, n);
        long[] fb = Arrays.copyOf(b, n);

        ntt(fa, false, p);
        ntt(fb, false, p);
        for (int i = 0; i < n; i++) {
            fa[i] = (fa[i] * fb[i]) % p.mod;
        }
        ntt(fa, true, p);
        return fa;
    }

    static long crtCombine(long a1, long a2, long a3) {
        long m1 = P1.mod, m2 = P2.mod, m3 = P3.mod;
        long M = m1 * m2;
        long invM1M2 = modInverse(m1, m2);

        long diff = (a2 - a1) % m2;
        if (diff < 0)
            diff += m2;
        long term1 = (diff * invM1M2) % m2;
        long x = a1 + term1 * m1;

        long MModM3 = M % m3;
        long invMM3 = modInverse(MModM3, m3);

        long diff2 = (a3 - (x % m3)) % m3;
        if (diff2 < 0)
            diff2 += m3;
        long k = (diff2 * invMM3) % m3;

        // x + k * M % TARGET_MOD
        // Note: x < M, so x fits in long
        // k * M can be up to m3 * M ~ 4.7 * 10^8 * 10^18 ~ 4.7 * 10^26, exceeds long!
        // We must compute using BigInteger or split M.
        // Or simply (x % TARGET_MOD + k * (M % TARGET_MOD)) % TARGET_MOD
        long xMod = x % TARGET_MOD;
        long MMod = M % TARGET_MOD;
        long res = (xMod + (k % TARGET_MOD) * MMod) % TARGET_MOD;
        return res;
    }

    static long[] convolutionCrt(long[] A, long[] B) {
        long[] r1 = convolve(A, B, P1);
        long[] r2 = convolve(A, B, P2);
        long[] r3 = convolve(A, B, P3);

        int n = r1.length;
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = crtCombine(r1[i], r2[i], r3[i]);
        }
        return res;
    }

    static class Solver {
        long[] fact, invFact;
        int maxK;

        Solver(int k) {
            maxK = k;
            fact = new long[k + 1];
            invFact = new long[k + 1];
            fact[0] = 1;
            for (int i = 1; i <= k; i++)
                fact[i] = (fact[i - 1] * i) % TARGET_MOD;
            invFact[k] = modInverse(fact[k], TARGET_MOD);
            for (int i = k - 1; i >= 0; i--)
                invFact[i] = (invFact[i + 1] * (i + 1)) % TARGET_MOD;
        }

        long solve(long n) {
            int k = maxK;
            long phi = TARGET_MOD - 1;
            long mExp = (n / k) % phi;

            long lambda = (power(2, mExp, TARGET_MOD) - 2 + TARGET_MOD) % TARGET_MOD;

            long[] H = new long[k + 1];
            for (int i = 0; i <= k; ++i) {
                H[i] = power(invFact[i], 16, TARGET_MOD);
            }

            long[] H2 = convolutionCrt(H, H);

            long[] U = new long[k + 1];
            for (int s = 0; s <= k; ++s) {
                long as = (power(fact[s], 16, TARGET_MOD) * H2[s]) % TARGET_MOD;
                U[s] = (as * invFact[s]) % TARGET_MOD;
            }

            long[] V = new long[k + 1];
            long lamPow = 1;
            for (int j = 0; j <= k; ++j) {
                V[j] = (lamPow * invFact[j]) % TARGET_MOD;
                lamPow = (lamPow * lambda) % TARGET_MOD;
            }

            long[] W = convolutionCrt(U, V);

            return (fact[k] * W[k]) % TARGET_MOD;
        }
    }

    public static String solve() {
        Solver s = new Solver(100000);
        return Long.toString(s.solve(10000000000000000L));
    }

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