import java.math.BigInteger;

public class Euler888 {

    static final long MOD = 912491249L;

    static class PeriodInfo {
        int period = 0;
        int start = 0;
        int[] seq;
    }

    static class GrundyData {
        int[] g;
        int maxG = 0;
        PeriodInfo even;
        PeriodInfo odd;
    }

    static int[] computeGrundy(int maxN, int[] maxGRef) {
        int[] g = new int[maxN + 1];
        int maxG = 0;
        int[] moves = { 1, 2, 4, 9 };

        for (int n = 1; n <= maxN; ++n) {
            long mask = 0;
            for (int mv : moves) {
                if (n >= mv) {
                    mask |= (1L << g[n - mv]);
                }
            }
            int half = n / 2;
            for (int a = 1; a <= half; ++a) {
                mask |= (1L << (g[a] ^ g[n - a]));
            }
            int mex = 0;
            while ((mask & (1L << mex)) != 0)
                ++mex;
            g[n] = mex;
            if (mex > maxG)
                maxG = mex;
        }
        maxGRef[0] = maxG;
        return g;
    }

    static PeriodInfo detectPeriod(int[] seq, int maxPeriod, int minReps) {
        int n = seq.length;
        for (int p = 1; p <= maxPeriod; ++p) {
            int L = p * minReps;
            if (L + p > n)
                continue;
            int startTail = n - L;
            boolean ok = true;
            for (int i = startTail; i + p < n; ++i) {
                if (seq[i] != seq[i + p]) {
                    ok = false;
                    break;
                }
            }
            if (!ok)
                continue;

            for (int s = 0; s + p < n; ++s) {
                boolean good = true;
                for (int i = s; i + p < n; ++i) {
                    if (seq[i] != seq[i + p]) {
                        good = false;
                        break;
                    }
                }
                if (good) {
                    PeriodInfo info = new PeriodInfo();
                    info.period = p;
                    info.start = s;
                    info.seq = seq;
                    return info;
                }
            }
        }
        return new PeriodInfo();
    }

    static GrundyData buildGrundyData(int maxN) {
        GrundyData data = new GrundyData();
        int[] maxGRef = new int[1];
        data.g = computeGrundy(maxN, maxGRef);
        data.maxG = maxGRef[0];

        int[] even = new int[maxN / 2];
        int[] odd = new int[(maxN + 1) / 2];

        int evenIdx = 0, oddIdx = 0;
        for (int k = 1; 2 * k <= maxN; ++k) {
            even[evenIdx++] = data.g[2 * k];
        }
        for (int k = 1; 2 * k - 1 <= maxN; ++k) {
            odd[oddIdx++] = data.g[2 * k - 1];
        }

        data.even = detectPeriod(even, 300, 6);
        data.odd = detectPeriod(odd, 300, 6);
        return data;
    }

    static void addCounts(PeriodInfo info, long total, long[] counts) {
        if (total <= 0)
            return;
        int[] seq = info.seq;
        int start = info.start;
        int period = info.period;

        if (total <= start) {
            for (int i = 0; i < total; ++i) {
                counts[seq[i]]++;
            }
            return;
        }

        for (int i = 0; i < start; ++i) {
            counts[seq[i]]++;
        }

        long rem = total - start;
        long[] freq = new long[counts.length];
        for (int i = 0; i < period; ++i) {
            freq[seq[start + i]]++;
        }

        long cycles = rem / period;
        long tail = rem % period;

        for (int g = 0; g < counts.length; ++g) {
            counts[g] += freq[g] * cycles;
        }
        for (int i = 0; i < tail; ++i) {
            counts[seq[start + i]]++;
        }
    }

    static long[] grundyCounts(long N, GrundyData data) {
        long[] counts = new long[data.maxG + 1];
        long totalEven = N / 2;
        long totalOdd = (N + 1) / 2;
        addCounts(data.even, totalEven, counts);
        addCounts(data.odd, totalOdd, counts);
        return counts;
    }

    static long[] buildComb(long c, int m) {
        long[] comb = new long[m + 1];
        BigInteger val = BigInteger.ONE;
        comb[0] = 1;
        BigInteger bMod = BigInteger.valueOf(MOD);
        for (int k = 1; k <= m; ++k) {
            val = val.multiply(BigInteger.valueOf(c + k - 1));
            val = val.divide(BigInteger.valueOf(k));
            comb[k] = val.mod(bMod).longValue();
        }
        return comb;
    }

    static class Term {
        int k;
        long v;

        Term(int k, long v) {
            this.k = k;
            this.v = v;
        }
    }

    static long computeS(long N, int m, GrundyData data) {
        long[] counts = grundyCounts(N, data);

        int bits = 0;
        while ((1 << bits) <= data.maxG)
            ++bits;
        int states = 1 << bits;

        long[][] dp = new long[states][m + 1];
        dp[0][0] = 1;

        for (int gval = 0; gval <= data.maxG; ++gval) {
            long c = counts[gval];
            if (c == 0)
                continue;

            long[] comb = buildComb(c, m);
            java.util.List<Term> evenTerms = new java.util.ArrayList<>();
            java.util.List<Term> oddTerms = new java.util.ArrayList<>();

            for (int k = 0; k <= m; ++k) {
                long v = comb[k];
                if (v == 0)
                    continue;
                if ((k & 1) == 1)
                    oddTerms.add(new Term(k, v));
                else
                    evenTerms.add(new Term(k, v));
            }

            long[][] nextDp = new long[states][m + 1];

            for (int mask = 0; mask < states; ++mask) {
                long[] cur = dp[mask];
                long[] destSame = nextDp[mask];
                long[] destXor = nextDp[mask ^ gval];

                for (int i = 0; i <= m; ++i) {
                    long curv = cur[i];
                    if (curv == 0)
                        continue;

                    for (Term term : evenTerms) {
                        int j = term.k;
                        if (i + j > m)
                            break;
                        long add = (curv * term.v) % MOD;
                        destSame[i + j] = (destSame[i + j] + add) % MOD;
                    }
                    for (Term term : oddTerms) {
                        int j = term.k;
                        if (i + j > m)
                            break;
                        long add = (curv * term.v) % MOD;
                        destXor[i + j] = (destXor[i + j] + add) % MOD;
                    }
                }
            }
            dp = nextDp;
        }

        return dp[0][m];
    }

    public static String solve() {
        GrundyData data = buildGrundyData(20000);
        return Long.toString(computeS(12491249L, 1249, data));
    }

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