public class Euler416 {
    static final long MOD = 1000000000;

    public static String solve() {
        int m = 10;
        long n = 1000000000000L;
        int p = 2 * m;
        int dim = 0;
        int[][] triples;
        int[][] idx = new int[p + 1][p + 1];
        java.util.List<int[]> tl = new java.util.ArrayList<>();
        for (int a = 0; a <= p; a++)
            for (int b = 0; b <= p - a; b++) {
                idx[a][b] = tl.size();
                tl.add(new int[] { a, b, p - a - b });
            }
        dim = tl.size();
        triples = tl.toArray(new int[0][]);
        int idxCP = idx[0][0];
        long[][] C = new long[p + 1][p + 1];
        C[0][0] = 1;
        for (int nn = 1; nn <= p; nn++) {
            C[nn][0] = C[nn][nn] = 1;
            for (int k = 1; k < nn; k++)
                C[nn][k] = C[nn - 1][k - 1] + C[nn - 1][k];
        }
        long[] allowed = new long[dim * dim], forbidden = new long[dim * dim];
        for (int inew = 0; inew < dim; inew++) {
            int at = triples[inew][0], bt = triples[inew][1], ct = triples[inew][2];
            for (int u = 0; u <= ct; u++)
                for (int v = 0; v <= ct - u; v++) {
                    int ao = u, bo = v + at, iold = idx[ao][bo];
                    long coeff = C[ct][u] * C[ct - u][v] % MOD;
                    allowed[inew * dim + iold] = (allowed[inew * dim + iold] + coeff) % MOD;
                }
        }
        for (int inew = 0; inew < dim; inew++) {
            int ct = triples[inew][2];
            if (ct != 0)
                continue;
            int iold = idx[0][triples[inew][0]];
            forbidden[inew * dim + iold] = 1;
        }
        long[] combined = new long[dim * dim];
        for (int i = 0; i < dim * dim; i++)
            combined[i] = (allowed[i] - forbidden[i] + MOD) % MOD;
        long internal = n - 2;
        long[] pv, pd;
        if (internal == 0) {
            pv = matId(dim);
            pd = new long[dim * dim];
        } else {
            long[][] res = powDeriv(combined, forbidden, internal, dim);
            pv = res[0];
            pd = res[1];
        }
        long sv = 0, sd = 0;
        for (int j = 0; j < dim; j++) {
            sv += allowed[idxCP * dim + j] * pv[j * dim + idxCP] % MOD;
            sd += allowed[idxCP * dim + j] * pd[j * dim + idxCP] % MOD;
        }
        return String.valueOf((sv % MOD + sd % MOD) % MOD);
    }

    static long[] matMul(long[] x, long[] y, int d) {
        long[] c = new long[d * d];
        for (int i = 0; i < d; i++)
            for (int k = 0; k < d; k++) {
                long xik = x[i * d + k];
                if (xik == 0)
                    continue;
                for (int j = 0; j < d; j++)
                    c[i * d + j] = (c[i * d + j] + xik * y[k * d + j]) % MOD;
            }
        return c;
    }

    static long[] matId(int d) {
        long[] m = new long[d * d];
        for (int i = 0; i < d; i++)
            m[i * d + i] = 1;
        return m;
    }

    static long[][] powDeriv(long[] base, long[] deriv, long exp, int d) {
        long[] rr = matId(d), rd = new long[d * d];
        while (exp > 0) {
            if ((exp & 1) != 0) {
                long[] nrd = new long[d * d];
                for (int i = 0; i < d; i++)
                    for (int j = 0; j < d; j++) {
                        long s1 = 0, s2 = 0;
                        for (int k = 0; k < d; k++) {
                            s1 += rd[i * d + k] * base[k * d + j] % MOD;
                            s2 += rr[i * d + k] * deriv[k * d + j] % MOD;
                        }
                        nrd[i * d + j] = (s1 + s2) % MOD;
                    }
                rd = nrd;
                rr = matMul(rr, base, d);
            }
            exp >>= 1;
            if (exp == 0)
                break;
            long[] nd = new long[d * d];
            for (int i = 0; i < d; i++)
                for (int j = 0; j < d; j++) {
                    long s1 = 0, s2 = 0;
                    for (int k = 0; k < d; k++) {
                        s1 += deriv[i * d + k] * base[k * d + j] % MOD;
                        s2 += base[i * d + k] * deriv[k * d + j] % MOD;
                    }
                    nd[i * d + j] = (s1 + s2) % MOD;
                }
            deriv = nd;
            base = matMul(base, base, d);
        }
        return new long[][] { rr, rd };
    }

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