import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

public class Euler670 {

    static final long MOD = 1000004321L;
    static final int COLORS = 4;

    static class State implements Comparable<State> {
        int rt, ct, rb, cb, prevVert;

        State(int rt, int ct, int rb, int cb, int prevVert) {
            this.rt = rt;
            this.ct = ct;
            this.rb = rb;
            this.cb = cb;
            this.prevVert = prevVert;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (!(o instanceof State))
                return false;
            State s = (State) o;
            return rt == s.rt && ct == s.ct && rb == s.rb && cb == s.cb && prevVert == s.prevVert;
        }

        @Override
        public int hashCode() {
            int h = rt;
            h = h * 1315423911 + (ct + 7);
            h = h * 1315423911 + (rb + 11);
            h = h * 1315423911 + (cb + 13);
            h = h * 1315423911 + (prevVert + 17);
            return h;
        }

        @Override
        public int compareTo(State o) {
            if (rt != o.rt)
                return Integer.compare(rt, o.rt);
            if (ct != o.ct)
                return Integer.compare(ct, o.ct);
            if (rb != o.rb)
                return Integer.compare(rb, o.rb);
            if (cb != o.cb)
                return Integer.compare(cb, o.cb);
            return Integer.compare(prevVert, o.prevVert);
        }
    }

    static List<State> initialStates() {
        List<State> init = new ArrayList<>();

        for (int v = 0; v < COLORS; ++v) {
            init.add(new State(0, v, 0, v, 1));
        }

        for (int lt = 1; lt <= 3; ++lt) {
            for (int lb = 1; lb <= 3; ++lb) {
                for (int a = 0; a < COLORS; ++a) {
                    for (int b = 0; b < COLORS; ++b) {
                        if (a == b)
                            continue;
                        init.add(new State(lt - 1, a, lb - 1, b, 0));
                    }
                }
            }
        }
        return init;
    }

    static class Pair {
        int first, second;

        Pair(int f, int s) {
            first = f;
            second = s;
        }
    }

    static List<State> nextStates(State s) {
        List<State> out = new ArrayList<>();

        boolean topChange = (s.rt == 0);
        boolean bottomChange = (s.rb == 0);

        if (s.rt == 0 && s.rb == 0) {
            for (int v = 0; v < COLORS; ++v) {
                if (v == s.ct || v == s.cb)
                    continue;
                out.add(new State(0, v, 0, v, 1));
            }
        }

        List<Pair> topOptions = new ArrayList<>();
        List<Pair> bottomOptions = new ArrayList<>();

        if (s.rt > 0) {
            topOptions.add(new Pair(s.rt - 1, s.ct));
        } else {
            for (int len = 1; len <= 3; ++len) {
                for (int color = 0; color < COLORS; ++color) {
                    if (color == s.ct)
                        continue;
                    topOptions.add(new Pair(len - 1, color));
                }
            }
        }

        if (s.rb > 0) {
            bottomOptions.add(new Pair(s.rb - 1, s.cb));
        } else {
            for (int len = 1; len <= 3; ++len) {
                for (int color = 0; color < COLORS; ++color) {
                    if (color == s.cb)
                        continue;
                    bottomOptions.add(new Pair(len - 1, color));
                }
            }
        }

        for (Pair top : topOptions) {
            for (Pair bottom : bottomOptions) {
                int ntRt = top.first;
                int ntCt = top.second;
                int ntRb = bottom.first;
                int ntCb = bottom.second;

                if (ntCt == ntCb)
                    continue;

                if (topChange && bottomChange && s.prevVert == 0)
                    continue;

                out.add(new State(ntRt, ntCt, ntRb, ntCb, 0));
            }
        }

        return out;
    }

    static long[][] multiply(long[][] x, long[][] y) {
        int n = x.length;
        long[][] z = new long[n][n];

        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < n; ++k) {
                long xik = x[i][k];
                if (xik == 0)
                    continue;
                for (int j = 0; j < n; ++j) {
                    long ykj = y[k][j];
                    if (ykj == 0)
                        continue;
                    z[i][j] = (z[i][j] + xik * ykj) % MOD;
                }
            }
        }
        return z;
    }

    static long[] multiplyVec(long[] v, long[][] m) {
        int n = m.length;
        long[] out = new long[n];

        for (int i = 0; i < n; ++i) {
            long vi = v[i];
            if (vi == 0)
                continue;
            for (int j = 0; j < n; ++j) {
                long mij = m[i][j];
                if (mij == 0)
                    continue;
                out[j] = (out[j] + vi * mij) % MOD;
            }
        }
        return out;
    }

    static class Solver {
        List<State> initStates;
        List<State> states;
        HashMap<State, Integer> index;
        long[][] transition;
        long[] initVector;

        Solver() {
            initStates = initialStates();
            buildReachable();
            buildTransition();
            buildInitialVector();
        }

        void buildReachable() {
            HashSet<State> seen = new HashSet<>();
            Queue<State> q = new LinkedList<>();

            for (State s : initStates) {
                if (seen.add(s)) {
                    q.offer(s);
                }
            }

            while (!q.isEmpty()) {
                State s = q.poll();
                for (State t : nextStates(s)) {
                    if (seen.add(t)) {
                        q.offer(t);
                    }
                }
            }

            states = new ArrayList<>(seen);
            Collections.sort(states);

            index = new HashMap<>();
            for (int i = 0; i < states.size(); ++i) {
                index.put(states.get(i), i);
            }
        }

        void buildTransition() {
            int n = states.size();
            transition = new long[n][n];

            for (int i = 0; i < n; ++i) {
                for (State t : nextStates(states.get(i))) {
                    int j = index.get(t);
                    transition[i][j] = (transition[i][j] + 1) % MOD;
                }
            }
        }

        void buildInitialVector() {
            int n = states.size();
            initVector = new long[n];
            for (State s : initStates) {
                int i = index.get(s);
                initVector[i] = (initVector[i] + 1) % MOD;
            }
        }

        long count(long n) {
            long[] vec = initVector.clone();
            long[][] p = new long[transition.length][];
            for (int i = 0; i < transition.length; i++) {
                p[i] = transition[i].clone();
            }
            long exp = n - 1;

            while (exp > 0) {
                if ((exp & 1) != 0) {
                    vec = multiplyVec(vec, p);
                }
                exp >>= 1;
                if (exp > 0) {
                    p = multiply(p, p);
                }
            }

            long ans = 0;
            for (int i = 0; i < states.size(); ++i) {
                State s = states.get(i);
                if (s.rt == 0 && s.rb == 0) {
                    ans = (ans + vec[i]) % MOD;
                }
            }
            return ans;
        }
    }

    public static String solve() {
        Solver solver = new Solver();
        long ans = solver.count(10000000000000000L);
        return Long.toString(ans);
    }

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