import java.math.BigInteger;

public class Euler984 {
    static final long MOD = 1000000007L;
    static final int K = 14;

    static final long[] INIT = {
            1L, 4L, 9L, 92L, 903L, 4411L, 14959L, 41083L, 98200L,
            212418L, 425756L, 803074L, 1441065L, 2479669L
    };

    static final long[] REC = {
            7L, MOD - 19L, 21L, 6L, MOD - 42L, 42L, MOD - 6L,
            MOD - 21L, 19L, MOD - 7L, 1L, 0L, 0L, 0L
    };

    static long modPow(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = BigInteger.valueOf(result).multiply(BigInteger.valueOf(base)).mod(BigInteger.valueOf(MOD))
                        .longValue();
            }
            base = BigInteger.valueOf(base).multiply(BigInteger.valueOf(base)).mod(BigInteger.valueOf(MOD)).longValue();
            exp >>= 1;
        }
        return result;
    }

    static long modInv(long x) {
        return modPow((x % MOD + MOD) % MOD, MOD - 2);
    }

    static long fEvenClosedFormMod(long n) {
        long x = n % MOD;
        long[] p = new long[9];
        p[0] = 1;
        for (int i = 1; i <= 8; ++i) {
            p[i] = BigInteger.valueOf(p[i - 1]).multiply(BigInteger.valueOf(x)).mod(BigInteger.valueOf(MOD))
                    .longValue();
        }

        long inv40320 = modInv(40320);
        long inv3360 = modInv(3360);
        long inv1440 = modInv(1440);
        long inv320 = modInv(320);
        long inv240 = modInv(240);
        long inv420 = modInv(420);
        long inv140 = modInv(140);

        long ans = 0;
        ans = (ans + BigInteger.valueOf(31).multiply(BigInteger.valueOf(p[8])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv40320)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(31).multiply(BigInteger.valueOf(p[7])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv3360)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(67).multiply(BigInteger.valueOf(p[6])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv1440)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(41).multiply(BigInteger.valueOf(p[5])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv320)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(313).multiply(BigInteger.valueOf(p[4])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv1440)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(MOD - 5699).multiply(BigInteger.valueOf(p[3])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv240)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(16049).multiply(BigInteger.valueOf(p[2])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv420)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + BigInteger.valueOf(29413).multiply(BigInteger.valueOf(p[1])).mod(BigInteger.valueOf(MOD))
                .multiply(BigInteger.valueOf(inv140)).mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
        ans = (ans + MOD - 419) % MOD;

        return ans;
    }

    static long[] combine(long[] a, long[] b) {
        long[] prod = new long[2 * K];
        for (int i = 0; i < K; ++i) {
            if (a[i] == 0)
                continue;
            for (int j = 0; j < K; ++j) {
                if (b[j] == 0)
                    continue;
                prod[i + j] = (prod[i + j] + BigInteger.valueOf(a[i]).multiply(BigInteger.valueOf(b[j]))
                        .mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
            }
        }

        for (int i = 2 * K - 2; i >= K; --i) {
            if (prod[i] == 0)
                continue;
            for (int j = 1; j <= K; ++j) {
                prod[i - j] = (prod[i - j] + BigInteger.valueOf(prod[i]).multiply(BigInteger.valueOf(REC[j - 1]))
                        .mod(BigInteger.valueOf(MOD)).longValue()) % MOD;
            }
        }

        long[] out = new long[K];
        System.arraycopy(prod, 0, out, 0, K);
        return out;
    }

    static long fMod(long n) {
        if (n == 0)
            return 0;
        if (n > 3 && (n & 1) == 0)
            return fEvenClosedFormMod(n);
        if (n <= K)
            return INIT[(int) (n - 1)] % MOD;

        long exp = n - 1;
        long[] poly = new long[K];
        long[] step = new long[K];
        poly[0] = 1;
        step[1] = 1;

        while (exp > 0) {
            if ((exp & 1) != 0) {
                poly = combine(poly, step);
            }
            step = combine(step, step);
            exp >>= 1;
        }

        long ans = 0;
        for (int i = 0; i < K; ++i) {
            ans = (ans + BigInteger.valueOf(poly[i]).multiply(BigInteger.valueOf(INIT[i])).mod(BigInteger.valueOf(MOD))
                    .longValue()) % MOD;
        }
        return ans;
    }

    public static String solve() {
        long target = 1000000000000000000L;
        return String.valueOf(fMod(target));
    }

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