import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Euler497 {

    private static final long MOD = 1000000000L;

    private static long[][] zeroMatrix() {
        return new long[3][3];
    }

    private static long[][] addMatrix(long[][] a, long[][] b, long mod) {
        long[][] out = zeroMatrix();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (mod == 0) {
                    out[i][j] = a[i][j] + b[i][j];
                } else {
                    out[i][j] = (a[i][j] + b[i][j]) % mod;
                }
            }
        }
        return out;
    }

    private static long[][] baseMatrixForOrientation(int from, int to) {
        long[][] m = zeroMatrix();
        m[from][to] = 1L;
        return m;
    }

    private static long modSub(long a, long b) {
        return (a >= b) ? (a - b) : (a + MOD - b);
    }

    private static long hitMod(long k, long x, long y, boolean ascending) {
        if (x == y)
            return 0L;
        if (ascending) {
            long a = modSub(y, x);
            long b = (x + y + MOD - 2L) % MOD;
            return (a * b) % MOD;
        }
        long a = modSub(x, y);
        long twoK = (2L * k) % MOD;
        long b = modSub(twoK, (x + y) % MOD);
        return (a * b) % MOD;
    }

    static class Tuple {
        int f, t, a;

        Tuple(int f, int t, int a) {
            this.f = f;
            this.t = t;
            this.a = a;
        }

        @Override
        public int hashCode() {
            return Objects.hash(f, t, a);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Tuple))
                return false;
            Tuple that = (Tuple) o;
            return f == that.f && t == that.t && a == that.a;
        }
    }

    static class OrientationIndex {
        Tuple[] triples;
        Map<Tuple, Integer> indexByTuple;

        OrientationIndex() {
            triples = new Tuple[] {
                    new Tuple(0, 1, 2), new Tuple(0, 2, 1), new Tuple(1, 0, 2),
                    new Tuple(1, 2, 0), new Tuple(2, 0, 1), new Tuple(2, 1, 0)
            };
            indexByTuple = new HashMap<>();
            for (int i = 0; i < triples.length; i++) {
                indexByTuple.put(triples[i], i);
            }
        }
    }

    private static long[][][] nextTransitionCounts(long[][][] prev, OrientationIndex ori, long mod) {
        long[][][] next = new long[6][][];
        for (int id = 0; id < 6; ++id) {
            Tuple t = ori.triples[id];
            int id1 = ori.indexByTuple.get(new Tuple(t.f, t.a, t.t));
            int id2 = ori.indexByTuple.get(new Tuple(t.a, t.t, t.f));

            long[][] cur = addMatrix(prev[id1], prev[id2], mod);
            if (mod == 0) {
                cur[t.a][t.f]++;
                cur[t.f][t.t]++;
                cur[t.t][t.a]++;
            } else {
                cur[t.a][t.f] = (cur[t.a][t.f] + 1) % mod;
                cur[t.f][t.t] = (cur[t.f][t.t] + 1) % mod;
                cur[t.t][t.a] = (cur[t.t][t.a] + 1) % mod;
            }
            next[id] = cur;
        }
        return next;
    }

    private static long eMod(long[][] c, long k, long a, long b, long cc) {
        long[] pos = { a, b, cc };
        long out = hitMod(k, b, a, false);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (c[i][j] == 0L)
                    continue;
                boolean ascending = (i < j);
                long h = hitMod(k, pos[i], pos[j], ascending);
                out = (out + c[i][j] * h) % MOD;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        int nMax = 10000;
        OrientationIndex ori = new OrientationIndex();
        int canonical = ori.indexByTuple.get(new Tuple(0, 2, 1));

        long[][][] curMod = new long[6][][];
        for (int id = 0; id < 6; ++id) {
            Tuple t = ori.triples[id];
            curMod[id] = baseMatrixForOrientation(t.f, t.t);
        }

        long p3 = 1L;
        long p6 = 1L;
        long p9 = 1L;
        long p10 = 1L;

        long total = 0L;

        for (int n = 1; n <= nMax; ++n) {
            if (n > 1) {
                curMod = nextTransitionCounts(curMod, ori, MOD);
            }

            p3 = (p3 * 3L) % MOD;
            p6 = (p6 * 6L) % MOD;
            p9 = (p9 * 9L) % MOD;
            p10 = (p10 * 10L) % MOD;

            long e = eMod(curMod[canonical], p10, p3, p6, p9);
            total = (total + e) % MOD;
        }

        System.out.printf("%09d\n", total);
    }
}