import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class Euler459 {

    static class NimMul {
        int[] fermat = { 1, 2, 4, 16, 256, 65536 };
        Map<Long, Integer> memo = new HashMap<>();

        int largestFermat(int x) {
            for (int i = fermat.length - 1; i >= 0; i--) {
                if (fermat[i] <= x)
                    return fermat[i];
            }
            return 1;
        }

        int mul(int a, int b) {
            if (a < b) {
                int temp = a;
                a = b;
                b = temp;
            }
            if (a == 0 || b == 0)
                return 0;
            if (b == 1)
                return a;

            long key = (((long) a) << 32) | (b & 0xFFFFFFFFL);
            Integer cached = memo.get(key);
            if (cached != null)
                return cached;

            int n = largestFermat(a);
            int a1 = a / n;
            int a0 = a % n;
            int b1 = b / n;
            int b0 = b % n;

            int p = mul(a0, b0);
            int q = mul(a0, b1) ^ mul(a1, b0);
            int r = mul(a1, b1);

            int shift = Integer.numberOfTrailingZeros(n);
            int res = p ^ ((q ^ r) << shift) ^ mul(r, n >> 1);

            memo.put(key, res);
            return res;
        }
    }

    static int nimPow(int base, int exp, NimMul nim) {
        int res = 1;
        int cur = base;
        int e = exp;
        while (e > 0) {
            if ((e & 1) != 0)
                res = nim.mul(res, cur);
            e >>= 1;
            if (e > 0)
                cur = nim.mul(cur, cur);
        }
        return res;
    }

    static class SeqResult {
        long[] counts;
        int totalXor;
        boolean overflow;
    }

    static SeqResult computeSequence(int n, int[] lengths, int limit) {
        SeqResult res = new SeqResult();
        int[] prefix = new int[n + 1];
        long[] counts = new long[limit];
        int[] lastSeen = new int[limit];
        Arrays.fill(lastSeen, -1);
        int[] freq = new int[limit];
        int[] used = new int[limit];

        for (int i = 1; i <= n; i++) {
            int pPrev = prefix[i - 1];
            int usedLen = 0;

            for (int l : lengths) {
                if (l > i)
                    break;
                int val = pPrev ^ prefix[i - l];
                if (val >= limit) {
                    res.overflow = true;
                    return res;
                }

                if (lastSeen[val] != i) {
                    lastSeen[val] = i;
                    freq[val] = 0;
                    used[usedLen++] = val;
                }
                freq[val]++;
            }

            int g = 0;
            while (lastSeen[g] == i) {
                g++;
            }

            if (g >= limit) {
                res.overflow = true;
                return res;
            }

            prefix[i] = pPrev ^ g;

            for (int k = 0; k < usedLen; k++) {
                int val = used[k];
                counts[val ^ g] += freq[val];
            }
        }

        res.counts = counts;
        res.totalXor = prefix[n];
        return res;
    }

    static class ComputeTask extends RecursiveTask<SeqResult> {
        int n;
        int[] lengths;
        int limit;

        ComputeTask(int n, int[] lengths, int limit) {
            this.n = n;
            this.lengths = lengths;
            this.limit = limit;
        }

        @Override
        protected SeqResult compute() {
            return computeSequence(n, lengths, limit);
        }
    }

    public static String solve() {
        int n = 1000000;
        List<Integer> hList = new ArrayList<>();
        for (long k = 1;; k++) {
            long t = k * (k + 1) / 2;
            if (t > n)
                break;
            hList.add((int) t);
        }
        int[] heights = hList.stream().mapToInt(i -> i).toArray();

        List<Integer> wList = new ArrayList<>();
        for (long k = 1; k * k <= n; k++) {
            wList.add((int) (k * k));
        }
        int[] widths = wList.stream().mapToInt(i -> i).toArray();

        int limit = 512;
        SeqResult rows = null;
        SeqResult cols = null;

        ForkJoinPool pool = new ForkJoinPool();

        while (true) {
            ComputeTask rowTask = new ComputeTask(n, heights, limit);
            ComputeTask colTask = new ComputeTask(n, widths, limit);

            rowTask.fork();
            cols = colTask.compute();
            rows = rowTask.join();

            if (!rows.overflow && !cols.overflow)
                break;
            limit <<= 1;
            if (limit >= (1 << 20)) {
                System.exit(1);
            }
        }

        NimMul nim = new NimMul();
        int totalXor = nim.mul(rows.totalXor, cols.totalXor);
        int maxValue = totalXor;

        for (int i = 0; i < limit; i++) {
            if (rows.counts[i] != 0 || cols.counts[i] != 0) {
                maxValue = Math.max(maxValue, i);
            }
        }

        int fieldSize = 2;
        while (fieldSize <= maxValue) {
            long next = (long) fieldSize * fieldSize;
            fieldSize = (int) next;
        }
        int invExp = fieldSize - 2;

        int[] inv = new int[limit];
        Arrays.fill(inv, -1);
        inv[0] = 0;
        if (limit > 1)
            inv[1] = 1;

        long sumRows = 0;
        long sumCols = 0;
        for (long c : rows.counts)
            sumRows += c;
        for (long c : cols.counts)
            sumCols += c;

        long answer = 0;
        if (totalXor == 0) {
            answer = rows.counts[0] * sumCols + cols.counts[0] * sumRows - rows.counts[0] * cols.counts[0];
        } else {
            for (int a = 1; a < limit; a++) {
                long countA = rows.counts[a];
                if (countA == 0)
                    continue;

                if (inv[a] == -1) {
                    inv[a] = nimPow(a, invExp, nim);
                }
                int b = nim.mul(inv[a], totalXor);
                if (b >= 0 && b < limit) {
                    answer += countA * cols.counts[b];
                }
            }
        }

        return Long.toString(answer);
    }

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