public class Euler711 {
    static final long kMod = 1000000007L;

    static long modPow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                result = (result * base) % kMod;
            }
            base = (base * base) % kMod;
            exp >>= 1;
        }
        return result;
    }

    public static String solve() {
        int nPower = 12345678;
        long ans = 0;

        long cK = 1;
        long sK = 0;
        long pow4K = 1;
        long oddPow4 = 4;

        for (int m = 0; m < nPower; ++m) {
            if ((m & 1) == 0) {
                long term = (cK * pow4K) % kMod;
                ans = (ans + term + sK) % kMod;

                long nextS = (2 * sK + (cK + 2) * pow4K) % kMod;
                sK = nextS;
                cK = (2 * cK) % kMod;
                pow4K = (4 * pow4K) % kMod;
            } else {
                ans = (ans + oddPow4 - 1) % kMod;
                if (ans < 0) {
                    ans += kMod;
                }
                oddPow4 = (4 * oddPow4) % kMod;
            }
        }

        if ((nPower & 1) == 0) {
            ans = (ans + modPow(2, nPower)) % kMod;
        }

        return Long.toString(ans);
    }

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