xorcubes003.cpp

#include <stdio.h>
#include <inttypes.h>
#include <assert.h>
#include <vector>

typedef uint32_t uint_t;
const uint32_t N = 1U << 16, P = 998244353;

static uint32_t cubes[N];
static uint32_t cnts[N];

static uint32_t solve(uint32_t n)
{
    if (n <= 2)
        return 0;

    uint32_t l = 0;
    for (uint32_t t = n; t; t >>= 1)
        l++;
    l--;
    uint32_t m = 1U << l;

    uint64_t res = 0;
    for (uint32_t i = 0; i < m; i++) {
        uint64_t res0 = 0;
        for (uint32_t j = 0; j < i; j++) {
            res0 = (res0 + cubes[j] * (uint64_t) cubes[i ^ j]) % P;
        }
        res = (res + res0 * cubes[i]) % P;
    }
    res = res * 2 * m % P;

    if (n == m)
        return res;

    uint64_t res1 = 0;
    for (uint32_t i = 0; i < m; i++) {
        for (uint32_t j = 0; j < i; j++) {
            res1 = (res1 + cubes[i ^ m] * (uint64_t) cubes[j ^ m] % P * cubes[i ^ j]) % P;
        }
    }
    res = (res + res1 * 6 * (n - m)) % P;

    for (uint32_t i = 0; i < m; i++)
        cnts[i] = 0;

    for (uint32_t i = m; i < n; i++) {
        for (uint32_t j = m; j < i; j++) {
            cnts[i ^ j]++;
        }
    }

    for (uint32_t a = 0; a < m; a++) {
        if (cnts[a] == 0)
            continue;
        uint64_t res2 = 0;
        for (uint32_t k = 0; k < m; k++) {
            res2 = (res2 + cubes[m ^ k] * (uint64_t) cubes[m ^ a ^ k]) % P;
        }
        res = (res + res2 * cubes[a] % P * cnts[a] * 6) % P;
    }

    return (res + solve(n - m)) % P;
}


int main()
{
    for (uint64_t i = 0; i < N; i++) {
        cubes[i] = (i * i % P) * i % P;
    }

    uint32_t n = 0;
    int st = scanf("%u", &n);
    assert (st == 1);
    assert (n < N);
    n++;

    uint32_t res = solve(n);
    printf("%u\n", res);

    return 0;
}