Consider a binary string of length $$$p$$$. Then we can notice that the number of strings with exactly $$$k$$$ ones is $$$\binom{n}{k}$$$. Then we can notice there is exactly one binary string with $$$0$$$ ones or $$$p$$$ ones. Therefore we can notice that $$$\binom{p}{0} \equiv \binom{p}{p} \equiv 1 \mod p$$$.

Let us now consider a binary string with $$$0 < k < p$$$ ones. Let that string be $$$s_0s_1\ldots s_{p-1}$$$. If we can group all strings with $$$k$$$ ones, into groups of size $$$p$$$, then the total number of strings is some multiple of $$$p$$$. We will now prove that all the cyclic shifts of $$$s$$$ are distinct, and there are exactly $$$p$$$ of them.

If there are two equal cyclic shifts of $$$s$$$, then there exists $$$0 < t < p$$$ such that $$$s_{i} = s_{i + t}$$$, considering all indices $$$\mod p$$$. Then we can notice $$$s_{i} = s_{i + lt}$$$ for all $$$l$$$. However $$$i + lt \mod p$$$ can be any value for the right choice of $$$l$$$. Therefore that means all elements of $$$s$$$ must be equal for a cyclic shift to be equal to another. However since $$$0 < k < n$$$, this is not true.

Therefore we can notice $$$\binom{p}{k} \equiv 0 \mod p$$$ for all $$$0 < k < p$$$ and $$$1$$$ otherwise.

Consider $$$\binom{p}{k} = p! / k! / (p - k)!$$$. Notice $$$p$$$ only divides $$$p!$$$ when $$$0 < k < p$$$, therefore it must be a multiple of $$$p$$$.

We can also notice that this means $$$(1 + x)^p = 1 + x^p \mod p$$$.

We need to count the number of subsets of $$$[1, p^t]$$$ with exactly $$$k$$$ elements, $$$\mod p$$$. We will now define the most important operation. Consider any set of $$$p$$$ elements in $$$[1, p^t]$$$. Then any solution where there are $$$0 < l < p$$$ elements used in those $$$p$$$ elements can be put into groups of multiples of $$$p$$$. Because we can keep the rest of the elements the same, and just pick any $$$l$$$ from these $$$p$$$ elements. Therefore the number of solutions $$$\mod p$$$, is the same if we only consider the solutions where all $$$p$$$ are picked, or all $$$p$$$ aren't picked.

Let's call these groups a block. Notice that the same argument works on any $$$p$$$ blocks of equal size. We can do these operations repeatedly on $$$p^t$$$, and end up with exactly $$$1$$$ block of size $$$p^t$$$. Therefore $$$\binom{p^t}{k} \equiv 0 \mod p$$$, except when $$$k = 0$$$ or $$$k = p^t$$$, where we can either pick the whole block or nothing.

Consider

. By induction we can notice this is $$$1 + x^{p^t}$$$. (Do you see a similarity with the block argument?)

If $$$n = \sum_t d_t \times p^t$$$, and we force $$$0 \le d_t < p$$$, then $$$d_t$$$ is unique, and is the digits of $$$n$$$ in base $$$p$$$. We can do a similar repeated block operation, but this time we get $$$d_t$$$ blocks of size $$$p^t$$$. Notice that similarly $$$k$$$ has a similar representtaion $$$k = \sum d^{k}_t \times p^t$$$. with $$$0 \le d^{k}_t < p$$$. Any other representation would require at least $$$p$$$ blocks of some power of $$$p$$$. If we pick blocks from $$$n$$$, we cannot get $$$p$$$ blocks of the same size, so those representations of $$$k$$$ are impossible.

Therefore we need to pick exactly $$$d_^{k}_t$$$ blocks of size $$$p^t$$$ from $$$d_t$$$ blocks. Therefore

The claim is effectively the same, except we write it as

Consider Koxia and Sequences. We need to find the xor of $$$a_i$$$ over all $$$i$$$ over all arrays with $$$sum(a) = x$$$ and $$$OR(a) = y$$$ for $$$0 \le y < 2^{20}, 1 \le n < 2^{40}, 0 \le x < 2^{60}$$$. Notice that the xor of $$$a_i$$$ over all arrays is equal by symmetry. So if $$$n$$$ is even, then the answer is trivially $$$0$$$.

So now let's consider only odd $$$n$$$. Then we just need the xor of $$$a_1$$$ over all arrays. Instead of considering fixed $$$y$$$, let's do inclusion exclusion over all submasks of $$$y$$$. So now our problem reduces to solving for $$$sum(a) = x$$$, and you only use some subsets of bits of $$$y$$$, $$$y'$$$ in $$$a$$$.

Notice that if some bitset appears $$$n_b$$$ times in $$$a$$$, then there are $$$\binom{n}{n_b}$$$ ways to reshuffle that bit in $$$a$$$. If that is even, and that bit appears in $$$a_1$$$, with probability $$$n_b / n$$$ then it appears an even number of times, Therefore $$$n_b$$$ must be a submask of $$$n$$$ for the solution to contribute.

Notice that now we have to pick some pairs of bits $$$2^{b_1}$$$ from $$$n$$$ and $$$2^{b_2}$$$ from $$$y'$$$, and add $$$2^{b_1 + b_2}$$$ over all pairs. So we now consider this a block of size $$$2^{b_1 + b_2}$$$, which needs to have a constant sum, $$$x$$$. Now we can use the lucas operation, picking any 2 blocks and forcing us to use either both or none. This will result in us getting the blocks which corresponds to the bits of $$$ny'$$$. Now the only we go to get $$$x$$$ an odd number of times, is if $$$x$$$ is a submask of $$$ny'$$$.

This just gets us the number of solutions. For a bit $$$b$$$ to be appear an odd number of times, the number of arrays where the bit appears odd number of times, must be odd. If the bit appears an odd number of times, then there is a block of $$$2^b$$$ that is forced, and the rest can be arbitrarily picked. So then we want to solve the same problem, but with $$$x - 2^i$$$ and $$$ny' - 2^i$$$.

Now by solving for every bit and inclusion exclusion over all submasks $$$y'$$$, we can solve the problem.