public class Euler763 {
    static int threshold(int n) {
        return (n + 1) * (n + 2) / 2;
    }

    static int maxNForM(int m) {
        int n = 0;
        while (threshold(n + 1) <= m) {
            ++n;
        }
        return n;
    }

    static long solveA2(int targetM, long modValue) {
        int nmax = maxNForM(targetM);
        int ring = nmax + 8;
        int nalloc = nmax + 2;

        long[][] u = new long[nalloc + 1][(nalloc + 2) * ring];
        long[][] v = new long[nalloc + 1][(nalloc + 2) * ring];
        long[] a = new long[ring];
        long[] f0 = new long[ring];
        a[0] = 1L;

        for (int m = 0; m <= targetM; ++m) {
            int cur = m % ring;

            for (int n = 1; n <= nmax; ++n) {
                for (int k = 1; k <= n; ++k) {
                    int idx = k * ring + cur;
                    u[n][idx] = 0L;
                    v[n][idx] = 0L;
                }
            }

            for (int n = 1; n <= nmax; ++n) {
                if (m < threshold(n)) {
                    continue;
                }

                for (int k = 1; k <= n; ++k) {
                    int h = (k < n) ? k : (k - 1);

                    long uSum = getU(u, f0, nalloc, ring, n, k, m - n - 2)
                            + getV(v, f0, nalloc, ring, n + 1, 1, m - n - 3)
                            + getU(u, f0, nalloc, ring, n + 1, k + 1, m - n - 3)
                            + getU(u, f0, nalloc, ring, n - 1, h, m - n - 1)
                            + getV(v, f0, nalloc, ring, n, 1, m - n - 2)
                            + getU(u, f0, nalloc, ring, n, h + 1, m - n - 2);

                    long vSum = getV(v, f0, nalloc, ring, n, k, m - n - 2)
                            + getV(v, f0, nalloc, ring, n + 1, k + 1, m - n - 3)
                            + ((k == n) ? 2L : 1L) * getU(u, f0, nalloc, ring, n + 1, 1, m - n - 3)
                            + getV(v, f0, nalloc, ring, n - 1, h, m - n - 1)
                            + getV(v, f0, nalloc, ring, n, h + 1, m - n - 2)
                            + ((k == n) ? 2L : 1L) * getU(u, f0, nalloc, ring, n, 1, m - n - 2);

                    int idx = k * ring + cur;
                    u[n][idx] = uSum % modValue;
                    v[n][idx] = vSum % modValue;
                }
            }

            long f0Sum = getA(a, ring, m - 1)
                    + 4L * getF0(f0, ring, m - 2)
                    + 2L * getU(u, f0, nalloc, ring, 1, 1, m - 3)
                    + getV(v, f0, nalloc, ring, 1, 1, m - 3);
            f0[cur] = f0Sum % modValue;

            if (m >= 1) {
                long aSum = 3L * getA(a, ring, m - 1) + 3L * getF0(f0, ring, m - 2);
                a[cur] = aSum % modValue;
            }
        }

        return a[targetM % ring];
    }

    static long getA(long[] a, int ring, int m) {
        if (m < 0)
            return 0L;
        return a[m % ring];
    }

    static long getF0(long[] f0, int ring, int m) {
        if (m < 0)
            return 0L;
        return f0[m % ring];
    }

    static long getU(long[][] u, long[] f0, int nalloc, int ring, int n, int k, int m) {
        if (m < 0)
            return 0L;
        if (n == 0)
            return (k == 0) ? getF0(f0, ring, m) : 0L;
        if (n < 0 || n > nalloc || k < 1 || k > n || m < threshold(n))
            return 0L;
        int idx = k * ring + (m % ring);
        return u[n][idx];
    }

    static long getV(long[][] v, long[] f0, int nalloc, int ring, int n, int k, int m) {
        if (m < 0)
            return 0L;
        if (n == 0)
            return (k == 0) ? getF0(f0, ring, m) : 0L;
        if (n < 0 || n > nalloc || k < 1 || k > n || m < threshold(n))
            return 0L;
        int idx = k * ring + (m % ring);
        return v[n][idx];
    }

    static long DMod(int n, long mod) {
        return solveA2(n - 1, mod);
    }

    public static String solve() {
        long ans = DMod(10000, 1000000000L);
        return String.format("%09d", ans);
    }

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