public class Euler706 {
    static final long kMod = 1000000007L;
    static final int kStates = 243;

    static int encode(int pref, int n0, int n1, int n2, int fmod) {
        return ((((pref * 3 + n0) * 3 + n1) * 3 + n2) * 3 + fmod);
    }

    public static String solve() {
        int d = 100000;
        int[][] nxt = new int[kStates][3];

        for (int id = 0; id < kStates; ++id) {
            int x = id;
            int fmod = x % 3;
            x /= 3;
            int n2 = x % 3;
            x /= 3;
            int n1 = x % 3;
            x /= 3;
            int n0 = x % 3;
            x /= 3;
            int pref = x % 3;

            for (int cls = 0; cls < 3; ++cls) {
                int np = (pref + cls) % 3;
                int[] ncnt = { n0, n1, n2 };
                int add = ncnt[np];
                int nf = (fmod + add) % 3;
                ncnt[np] = (ncnt[np] + 1) % 3;
                nxt[id][cls] = encode(np, ncnt[0], ncnt[1], ncnt[2], nf);
            }
        }

        long[] dp = new long[kStates];
        dp[encode(0, 1, 0, 0, 0)] = 1L;

        for (int pos = 1; pos <= d; ++pos) {
            long[] ndp = new long[kStates];
            int[] mult = (pos == 1) ? new int[] { 3, 3, 3 } : new int[] { 4, 3, 3 };

            for (int id = 0; id < kStates; ++id) {
                long ways = dp[id];
                if (ways == 0)
                    continue;
                for (int cls = 0; cls < 3; ++cls) {
                    int to = nxt[id][cls];
                    ndp[to] = (ndp[to] + ways * mult[cls]) % kMod;
                }
            }
            dp = ndp;
        }

        long ans = 0;
        for (int id = 0; id < kStates; ++id) {
            if (id % 3 == 0) {
                ans = (ans + dp[id]) % kMod;
            }
        }
        return Long.toString(ans);
    }

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