import java.util.Arrays;

public class Euler1000 {
    static final long MOD = 1_000_000_007L;

    static int paritySign(int value) {
        int parity = 0;
        while (value > 0) {
            parity ^= 1;
            value &= value - 1;
        }
        return parity == 0 ? 1 : -1;
    }

    static int bitCount(int limit) {
        int bits = 0;
        while ((1 << bits) <= limit) {
            ++bits;
        }
        return bits;
    }

    static int highestBit(int value) {
        int bit = 0;
        while ((1 << (bit + 1)) <= value) {
            ++bit;
        }
        return bit;
    }

    // Returns { value, upperBound }.
    static long[] parityAndCandidate(int n) {
        int bits = bitCount(n);
        int[] count = new int[bits];
        int[] discrepancy = new int[bits];

        for (int value = 1; value <= n; ++value) {
            int sign = paritySign(value);
            for (int bit = 0; bit < bits; ++bit) {
                if (((value >> bit) & 1) != 0) {
                    ++count[bit];
                    discrepancy[bit] += sign;
                }
            }
        }

        long upperBound = 0;
        long valueSum = 0;
        for (int bit = 0; bit < bits; ++bit) {
            long weight = 1L << bit;
            long m = count[bit];
            int s = discrepancy[bit];
            upperBound += weight * ((m * m) / 4);
            valueSum += weight * ((m * m - (long) s * s) / 4);
        }

        return new long[] { valueSum, upperBound };
    }

    static long maxAndValue(int n) {
        long[] candidate = parityAndCandidate(n);
        assert candidate[0] == candidate[1];
        return candidate[0];
    }

    static long bruteMaxAnd(int n) {
        long best = 0;
        for (long mask = 0; mask < (1L << n); ++mask) {
            long current = 0;
            for (int a = 1; a <= n; ++a) {
                for (int b = a + 1; b <= n; ++b) {
                    boolean sideA = ((mask >> (a - 1)) & 1L) != 0;
                    boolean sideB = ((mask >> (b - 1)) & 1L) != 0;
                    if (sideA != sideB) {
                        current += (a & b);
                    }
                }
            }
            best = Math.max(best, current);
        }
        return best;
    }

    static long maxXorSum(int n) {
        int[] squares = new int[n + 1];
        for (int value = 1; value <= n; ++value) {
            squares[value] = value * value;
        }

        // Pack each edge as (weight << 22) | (from << 11) | to so that sorting
        // the long[] orders edges by weight first. from, to <= 1000 < 2^11 and
        // weight = a^2 ^ b^2 < 2^21 for a, b <= 1000.
        long[] edges = new long[n * (n - 1)];
        int idx = 0;
        for (int from = 1; from <= n; ++from) {
            for (int to = 1; to <= n; ++to) {
                if (from != to) {
                    long weight = squares[from] ^ squares[to];
                    edges[idx++] = (weight << 22) | ((long) from << 11) | to;
                }
            }
        }

        Arrays.sort(edges);

        long[] best = new long[n + 1];
        long answer = 0;

        int index = 0;
        int total = edges.length;
        int[] pendingTo = new int[total];
        long[] pendingValue = new long[total];

        while (index < total) {
            long weight = edges[index] >> 22;
            int pending = 0;

            while (index < total && (edges[index] >> 22) == weight) {
                int from = (int) ((edges[index] >> 11) & 0x7FF);
                int to = (int) (edges[index] & 0x7FF);
                long candidate = best[from] + weight;
                pendingTo[pending] = to;
                pendingValue[pending] = candidate;
                ++pending;
                answer = Math.max(answer, candidate);
                ++index;
            }

            for (int p = 0; p < pending; ++p) {
                best[pendingTo[p]] = Math.max(best[pendingTo[p]], pendingValue[p]);
            }
        }

        return answer;
    }

    static long countUnreachableNim(int n) {
        if (n <= 1) {
            return 0;
        }

        int topBit = highestBit(n - 1);
        long total = 0;
        for (int targetBit = 0; targetBit <= topBit; ++targetBit) {
            long[] dp = new long[8];
            dp[7] = 1;

            for (int bit = topBit; bit >= 0; --bit) {
                long[] next = new long[8];
                int limitBit = ((n - 1) >> bit) & 1;

                for (int mask = 0; mask < 8; ++mask) {
                    if (dp[mask] == 0) {
                        continue;
                    }
                    for (int a = 0; a <= 1; ++a) {
                        for (int b = 0; b <= 1; ++b) {
                            for (int c = 0; c <= 1; ++c) {
                                if (bit > targetBit && ((a ^ b ^ c) != 0)) {
                                    continue;
                                }
                                if (bit == targetBit && (a == 0 || b == 0 || c == 0)) {
                                    continue;
                                }

                                int[] chosen = { a, b, c };
                                boolean valid = true;
                                int nextMask = 0;
                                for (int index = 0; index < 3; ++index) {
                                    if (((mask >> index) & 1) == 0) {
                                        continue;
                                    }
                                    if (chosen[index] > limitBit) {
                                        valid = false;
                                        break;
                                    }
                                    if (chosen[index] == limitBit) {
                                        nextMask |= 1 << index;
                                    }
                                }

                                if (valid) {
                                    next[nextMask] += dp[mask];
                                }
                            }
                        }
                    }
                }

                dp = next;
            }

            for (long value : dp) {
                total += value;
            }
        }

        return total;
    }

    static long bruteUnreachableNim(int n) {
        long total = 0;
        for (int a = 0; a < n; ++a) {
            for (int b = 0; b < n; ++b) {
                for (int c = 0; c < n; ++c) {
                    int nimSum = a ^ b ^ c;
                    if (nimSum == 0) {
                        continue;
                    }
                    int bit = highestBit(nimSum);
                    if (((a >> bit) & 1) != 0 && ((b >> bit) & 1) != 0 && ((c >> bit) & 1) != 0) {
                        ++total;
                    }
                }
            }
        }
        return total;
    }

    static long mulMod(long lhs, long rhs) {
        return (lhs % MOD) * (rhs % MOD) % MOD;
    }

    static long metaValue(int index, long first, long second, long third) {
        if (index == 0) {
            return first % MOD;
        }
        if (index == 1) {
            return second % MOD;
        }
        if (index == 2) {
            return third % MOD;
        }

        long a = first % MOD;
        long b = second % MOD;
        long c = third % MOD;
        for (int current = 3; current <= index; ++current) {
            long next = mulMod(mulMod(c, b), a);
            a = b;
            b = c;
            c = next;
        }

        return c;
    }

    static void runCheckpoints() {
        assert bruteMaxAnd(10) == 50;
        assert maxAndValue(10) == 50;
        long[] targetAnd = parityAndCandidate(1000);
        assert targetAnd[0] == targetAnd[1];
        assert maxXorSum(4) == 71;
        assert maxXorSum(10) == 702;

        for (int n = 1; n <= 20; ++n) {
            assert countUnreachableNim(n) == bruteUnreachableNim(n);
        }
        assert countUnreachableNim(10) == 123;
    }

    public static void main(String[] args) {
        runCheckpoints();

        long maxAnd = maxAndValue(1000);
        long maxXor = maxXorSum(1000);
        long unreachableNim = countUnreachableNim(1000);
        assert metaValue(4, maxAnd, maxXor, unreachableNim) == 457_587_170L;

        System.out.println(metaValue(1000, maxAnd, maxXor, unreachableNim));
    }
}