import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Euler490 {

    private static final long MOD = 1000000000L;

    static class State {
        int k;
        int[] deg;
        int[] comp;

        State(int k, int[] deg, int[] comp) {
            this.k = k;
            this.deg = deg;
            this.comp = comp;
        }

        @Override
        public int hashCode() {
            int h = k;
            for (int i = 0; i < k; ++i)
                h = h * 3 + deg[i];
            for (int i = 0; i < k; ++i)
                h = h * 3 + comp[i];
            return h;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof State))
                return false;
            State s = (State) obj;
            if (k != s.k)
                return false;
            for (int i = 0; i < k; ++i)
                if (deg[i] != s.deg[i])
                    return false;
            for (int i = 0; i < k; ++i)
                if (comp[i] != s.comp[i])
                    return false;
            return true;
        }
    }

    private static int[] canonicalize(int k, int[] comp) {
        int[] map = new int[comp.length + 5];
        Arrays.fill(map, -1);
        int nxt = 0;
        int[] newComp = Arrays.copyOf(comp, comp.length);
        for (int i = 0; i < k; ++i) {
            int c = comp[i];
            if (map[c] == -1)
                map[c] = nxt++;
            newComp[i] = map[c];
        }
        return newComp;
    }

    private static boolean compsAllSame(int k, int[] comp) {
        for (int i = 1; i < k; ++i) {
            if (comp[i] != comp[0])
                return false;
        }
        return true;
    }

    private static Map<State, Integer> transitions(State s, boolean remove, boolean removeIsOne) {
        Map<State, Integer> out = new HashMap<>();
        int k = s.k;
        List<int[]> subsets = new ArrayList<>();
        subsets.add(new int[0]);
        for (int i = 0; i < k; ++i)
            subsets.add(new int[] { i });
        for (int i = 0; i < k; ++i) {
            for (int j = i + 1; j < k; ++j) {
                subsets.add(new int[] { i, j });
            }
        }

        for (int[] subset : subsets) {
            if (subset.length == 2 && s.comp[subset[0]] == s.comp[subset[1]])
                continue;

            boolean ok = true;
            for (int idx : subset) {
                if (s.deg[idx] >= 2) {
                    ok = false;
                    break;
                }
            }
            if (!ok)
                continue;

            int[] ndeg = Arrays.copyOf(s.deg, k + 1);
            int[] ncomp = Arrays.copyOf(s.comp, k + 1);
            int nk = k + 1;

            for (int idx : subset)
                ndeg[idx]++;

            int newComp = 0;
            if (subset.length == 0) {
                int maxc = -1;
                for (int i = 0; i < k; ++i)
                    maxc = Math.max(maxc, ncomp[i]);
                newComp = maxc + 1;
            } else if (subset.length == 1) {
                newComp = ncomp[subset[0]];
            } else {
                int compA = ncomp[subset[0]];
                int compB = ncomp[subset[1]];
                newComp = Math.min(compA, compB);
                for (int i = 0; i < k; ++i) {
                    if (ncomp[i] == compA || ncomp[i] == compB)
                        ncomp[i] = newComp;
                }
            }

            ndeg[k] = subset.length;
            ncomp[k] = newComp;

            if (remove) {
                int leavingDeg = ndeg[0];
                if (removeIsOne) {
                    if (leavingDeg != 1)
                        continue;
                } else {
                    if (leavingDeg != 2)
                        continue;
                }

                int leavingComp = ncomp[0];

                for (int i = 1; i <= k; ++i) {
                    ndeg[i - 1] = ndeg[i];
                    ncomp[i - 1] = ncomp[i];
                }
                ndeg[k] = 0;
                ncomp[k] = 0;
                nk = k;

                boolean present = false;
                for (int i = 0; i < nk; ++i) {
                    if (ncomp[i] == leavingComp) {
                        present = true;
                        break;
                    }
                }
                if (!present)
                    continue;
            }

            ncomp = canonicalize(nk, ncomp);
            State nst = new State(nk, ndeg, ncomp);
            out.put(nst, out.getOrDefault(nst, 0) + 1);
        }
        return out;
    }

    private static boolean isFinalGeneric(State s) {
        return s.k == 3 && compsAllSame(s.k, s.comp) && s.deg[0] == 2 && s.deg[1] == 2 && s.deg[2] == 1;
    }

    static class Model {
        int d;
        List<State> states;
        long[][] A;
        long[] v4;
        long[] c;
    }

    private static Model buildModel() {
        Map<State, Long> dp = new HashMap<>();
        State start = new State(1, new int[] { 0 }, new int[] { 0 });
        dp.put(start, 1L);

        for (int t = 1; t <= 3; ++t) {
            boolean remove = (t + 1 >= 4);
            boolean removeIsOne = remove && (t - 2 == 1);
            Map<State, Long> next = new HashMap<>();
            for (Map.Entry<State, Long> kv : dp.entrySet()) {
                State st = kv.getKey();
                long count = kv.getValue();
                for (Map.Entry<State, Integer> tr : transitions(st, remove, removeIsOne).entrySet()) {
                    long add = (count * tr.getValue()) % MOD;
                    next.put(tr.getKey(), (next.getOrDefault(tr.getKey(), 0L) + add) % MOD);
                }
            }
            dp = next;
        }

        Model model = new Model();
        model.states = new ArrayList<>();
        Map<State, Integer> idxMap = new HashMap<>();
        model.d = 0;
        Queue<State> q = new LinkedList<>();

        for (State st : dp.keySet()) {
            if (!idxMap.containsKey(st)) {
                idxMap.put(st, model.d++);
                model.states.add(st);
                q.add(st);
            }
        }

        while (!q.isEmpty()) {
            State cur = q.poll();
            for (Map.Entry<State, Integer> tr : transitions(cur, true, false).entrySet()) {
                State nst = tr.getKey();
                if (!idxMap.containsKey(nst)) {
                    idxMap.put(nst, model.d++);
                    model.states.add(nst);
                    q.add(nst);
                }
            }
        }

        int d = model.d;
        model.A = new long[d][d];
        for (int j = 0; j < d; ++j) {
            State cur = model.states.get(j);
            for (Map.Entry<State, Integer> tr : transitions(cur, true, false).entrySet()) {
                int i = idxMap.get(tr.getKey());
                model.A[i][j] = (model.A[i][j] + tr.getValue()) % MOD;
            }
        }

        model.v4 = new long[d];
        for (Map.Entry<State, Long> kv : dp.entrySet()) {
            int id = idxMap.get(kv.getKey());
            model.v4[id] = (model.v4[id] + kv.getValue()) % MOD;
        }

        model.c = new long[d];
        for (int i = 0; i < d; ++i) {
            if (isFinalGeneric(model.states.get(i)))
                model.c[i] = 1;
        }

        return model;
    }

    private static long[][] mulMat(long[][] A, long[][] B) {
        int d = A.length;
        long[][] C = new long[d][d];
        for (int i = 0; i < d; ++i) {
            for (int k = 0; k < d; ++k) {
                if (A[i][k] == 0)
                    continue;
                for (int j = 0; j < d; ++j) {
                    long term = (A[i][k] * B[k][j]) % MOD;
                    C[i][j] = (C[i][j] + term) % MOD;
                }
            }
        }
        return C;
    }

    private static long[] mulMatVec(long[][] A, long[] v) {
        int d = A.length;
        long[] out = new long[d];
        for (int i = 0; i < d; ++i) {
            long sum = 0;
            for (int j = 0; j < d; ++j) {
                sum = (sum + A[i][j] * v[j]) % MOD;
            }
            out[i] = sum;
        }
        return out;
    }

    private static int idx3(int i, int j, int k, int d) {
        return (i * d + j) * d + k;
    }

    private static long[] transformTensor(long[] T, long[][] A) {
        int d = A.length;
        long[] U = new long[d * d * d];
        for (int a = 0; a < d; ++a) {
            for (int j = 0; j < d; ++j) {
                for (int k = 0; k < d; ++k) {
                    long sum = 0;
                    for (int i = 0; i < d; ++i) {
                        sum = (sum + A[i][a] * T[idx3(i, j, k, d)]) % MOD;
                    }
                    U[idx3(a, j, k, d)] = sum;
                }
            }
        }

        long[] V = new long[d * d * d];
        for (int a = 0; a < d; ++a) {
            for (int b = 0; b < d; ++b) {
                for (int k = 0; k < d; ++k) {
                    long sum = 0;
                    for (int j = 0; j < d; ++j) {
                        sum = (sum + A[j][b] * U[idx3(a, j, k, d)]) % MOD;
                    }
                    V[idx3(a, b, k, d)] = sum;
                }
            }
        }

        long[] W = new long[d * d * d];
        for (int a = 0; a < d; ++a) {
            for (int b = 0; b < d; ++b) {
                for (int c = 0; c < d; ++c) {
                    long sum = 0;
                    for (int k = 0; k < d; ++k) {
                        sum = (sum + A[k][c] * V[idx3(a, b, k, d)]) % MOD;
                    }
                    W[idx3(a, b, c, d)] = sum;
                }
            }
        }

        return W;
    }

    private static long evalTensor(long[] T, long[] v) {
        int d = v.length;
        long total = 0;
        for (int i = 0; i < d; ++i) {
            if (v[i] == 0)
                continue;
            for (int j = 0; j < d; ++j) {
                if (v[j] == 0)
                    continue;
                long vij = (v[i] * v[j]) % MOD;
                for (int k = 0; k < d; ++k) {
                    if (v[k] == 0)
                        continue;
                    long t = T[idx3(i, j, k, d)];
                    if (t == 0)
                        continue;
                    long term = (t * vij) % MOD;
                    term = (term * v[k]) % MOD;
                    total = (total + term) % MOD;
                }
            }
        }
        return total;
    }

    static class Powers {
        long[][][] APow;
        long[][] TPow;
    }

    private static Powers buildPowers(long[][] A, long[] c, int maxBits) {
        int d = A.length;
        Powers p = new Powers();
        p.APow = new long[maxBits][][];
        p.TPow = new long[maxBits][];

        p.APow[0] = A;
        long[] T1 = new long[d * d * d];
        for (int i = 0; i < d; ++i) {
            if (c[i] == 0)
                continue;
            for (int j = 0; j < d; ++j) {
                if (c[j] == 0)
                    continue;
                long cij = (c[i] * c[j]) % MOD;
                for (int k = 0; k < d; ++k) {
                    if (c[k] == 0)
                        continue;
                    T1[idx3(i, j, k, d)] = (cij * c[k]) % MOD;
                }
            }
        }
        p.TPow[0] = T1;

        for (int bit = 1; bit < maxBits; ++bit) {
            p.APow[bit] = mulMat(p.APow[bit - 1], p.APow[bit - 1]);
            long[] transformed = transformTensor(p.TPow[bit - 1], p.APow[bit - 1]);
            long[] merged = new long[d * d * d];
            for (int i = 0; i < d * d * d; ++i) {
                merged[i] = (p.TPow[bit - 1][i] + transformed[i]) % MOD;
            }
            p.TPow[bit] = merged;
        }
        return p;
    }

    private static long sumFrom4(long L, int d, long[] v4, Powers powers) {
        if (L < 4)
            return 0;
        long len = L - 3;
        long[] v = Arrays.copyOf(v4, v4.length);
        long sum = 0;
        int bit = 0;
        while (len > 0) {
            if ((len & 1) != 0) {
                sum = (sum + evalTensor(powers.TPow[bit], v)) % MOD;
                v = mulMatVec(powers.APow[bit], v);
            }
            len >>= 1;
            bit++;
        }
        return sum;
    }

    private static long computeSMod(long L, Model model, Powers powers) {
        long total = 0;
        if (L >= 1)
            total = (total + 1) % MOD;
        if (L >= 2)
            total = (total + 1) % MOD;
        if (L >= 3)
            total = (total + 1) % MOD;
        if (L >= 4)
            total = (total + sumFrom4(L, model.d, model.v4, powers)) % MOD;
        return total;
    }

    public static void main(String[] args) {
        long L = 100000000000000L;
        Model model = buildModel();

        long maxL = Math.max(L, 1000000L);
        long maxLen = (maxL >= 4) ? (maxL - 3) : 1;
        int maxBits = 0;
        while (maxBits < 63 && (1L << maxBits) <= maxLen)
            maxBits++;
        if (maxBits == 0)
            maxBits = 1;

        Powers powers = buildPowers(model.A, model.c, maxBits);
        long answer = computeSMod(L, model, powers);
        System.out.println(answer);
    }
}