#include <algorithm>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

// Direct distinct-part XOR knapsack modulo one prime.
// Output rows: k  d_k (mod p), where d_k counts distinct partitions of 2k
// with XOR zero.  This algorithm is independent of the signed-partition
// Walsh recurrence used for the main exact-count computation.

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cerr << "usage: distinct_xor_knapsack TOTAL_SIZE_MAX PRIME OUTPUT\n";
        return 2;
    }
    const int nmax = std::stoi(argv[1]);
    const std::uint32_t prime = static_cast<std::uint32_t>(std::stoul(argv[2]));
    const std::string output_path = argv[3];
    if (nmax < 0 || (nmax % 2) != 0) {
        throw std::invalid_argument("TOTAL_SIZE_MAX must be a nonnegative even integer");
    }

    int xor_size = 1;
    while (xor_size <= nmax) xor_size <<= 1;
    const std::size_t row_size = static_cast<std::size_t>(xor_size);
    std::vector<std::uint32_t> dp(static_cast<std::size_t>(nmax + 1) * row_size, 0U);
    dp[0] = 1U;

    for (int part = 1; part <= nmax; ++part) {
        for (int sum = nmax; sum >= part; --sum) {
            const int source_sum = sum - part;
            const std::uint32_t* src = dp.data() + static_cast<std::size_t>(source_sum) * row_size;
            std::uint32_t* dst = dp.data() + static_cast<std::size_t>(sum) * row_size;

            // XOR parity equals ordinary-sum parity, and XOR <= ordinary sum.
            // Thus only half of each source row can be nonzero.
            const int parity = source_sum & 1;
            for (int x = parity; x <= source_sum; x += 2) {
                const std::uint32_t value = src[x];
                if (value == 0U) continue;
                const int y = x ^ part;
                std::uint64_t total = static_cast<std::uint64_t>(dst[y]) + value;
                if (total >= prime) total -= prime;
                dst[y] = static_cast<std::uint32_t>(total);
            }
        }
    }

    std::ofstream out(output_path);
    if (!out) throw std::runtime_error("cannot open output file");
    for (int k = 0; 2 * k <= nmax; ++k) {
        out << k << ' ' << dp[static_cast<std::size_t>(2 * k) * row_size] << '\n';
    }
    return 0;
}
