public class Euler762 {
    static final long MOD = 1000000000L;

    static long C(int n) {
        long[] base = {
                1L, 1L, 2L, 4L, 9L, 20L, 46L, 105L, 243L
        };

        if (n < base.length) {
            return base[n];
        }

        long[] w = base.clone();
        for (int k = 9; k <= n; ++k) {
            long next = 0;
            next += 2L * w[8];
            next += 2L * w[7];
            next -= 1L * w[6];
            next -= 3L * w[5];
            next -= 5L * w[4];
            next += 4L * w[3];
            next -= 2L * w[2];
            next += 4L * w[1];

            next %= MOD;
            if (next < 0) {
                next += MOD;
            }

            for (int i = 0; i < 8; ++i) {
                w[i] = w[i + 1];
            }
            w[8] = next;
        }
        return w[8];
    }

    public static String solve() {
        return Long.toString(C(100000));
    }

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