public class Euler907 {

    static final long MOD = 1000000007L;

    static long sMod(long n) {
        if (n <= 0) {
            return 0;
        }

        long[] base = { 0, 2, 2, 6, 12, 16, 22, 36, 58, 82 };
        if (n <= 9) {
            return base[(int) n] % MOD;
        }

        long[] a = base.clone();
        for (long i = 10; i <= n; ++i) {
            long v = 0;
            v = (v + 2 * a[9]) % MOD;
            v = (v - 3 * a[8]) % MOD;
            v = (v + 5 * a[7]) % MOD;
            v = (v - 4 * a[6]) % MOD;
            v = (v + 4 * a[5]) % MOD;
            v = (v - 3 * a[4]) % MOD;
            v = (v + a[3]) % MOD;
            v = (v - a[2]) % MOD;
            if (v < 0) {
                v += MOD;
            }

            for (int j = 2; j <= 9; ++j) {
                a[j - 1] = a[j];
            }
            a[9] = v;
        }

        return a[9];
    }

    public static String solve() {
        return Long.toString(sMod(10000000));
    }

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