Let us call a basis \((S_1,S_2,\dots,S_K)\) of a sequence consisting of integers between \(0\) and \(2^M-1\) normal when it satisfies the following:

• \(0 < S_1 < S_2 < \dots < S_K < 2^M\) holds;
• the highest bit in \(S_i\) is \(0\) in \(S_j\), for each \((i,j)\) such that \(1 \le i < j \le K\).

The problem is solved if we find the sum, for all sequences of non-negative integers \(0 \le X_1 < X_2 < \dots < X_K < M\), of the products of the values below.

• The number of sequences \(A\) such that a normal basis of \(A\) consists of \(K\) vectors and the top bit of the \(i\)-th smallest vector is \(2^{X_i}\).
• The expected value of the answer to Xor Optimization Problem for a sequence with such a basis as above.
• The number of sequences of non-negative integers \(1 \le Y_1 < Y_2 < \dots < Y_K < 2^M\) such that the highest bit in \(Y_i\) is \(0\) in \(Y_j\) for each pair \(1 \le i < j \le K\) and the highest bit in \(Y_i\) is \(2^{X_i}\) for each \(1 \le i \le K\).

Let us find the number of sequences \(A\) such that a normal basis of \(A\) consists of \(K\) vectors and the top bit of the \(i\)-th smallest vector is \(2^{X_i}\). We are done if we find the number of sequences with the basis \({2^0,2^1,2^2,\dots,2^{K-1}}\).

Let us start with \(S=\{ \}\) and do the operations below \(N\) times in total.

• Choose one of the \(2^{|S|}\) non-negative integers obtained as the \(\mathrm{XOR}\) of some subset of the elements in \(S\), and append it to the end of \(A\).
• Choose an integer \(i\) such that \(0 \le i < 2^K\) and cannot be obtained as the \(\mathrm{XOR}\) of any subset of the elements in \(S\), and append it to the ends of \(A\) and \(S\); there are \(2^K-2^{|S|}\) such indices \(i\).

Here, the second operation must be done exactly \(K\) times out of \(N\).

There are \([x^{N-K}]\prod_{i=0}^{K} \frac{1}{1-2^ix} \times \prod_{i=0}^{K-1} (2^K-2^i)\) sequences \(A\) that can be made this way. Now, let \(f_K(x) = \prod_{i=0}^{K} \frac{1}{1-2^ix}\).

We have \((1-x)f_K(x) = (1-2^{K+1}x)f_K(2x)\). By observing the coefficients of \(x^{i+1}\) on both sides, we get \([x^{i+1}](1-2^{i+1}) f_K(x) = [x^i](1-2^{K+i+1})f_K(x)\), from \([x^{i+1}] f_K(x) - [x^i] f_K(x) = [x^{i+1}] 2^{i+1}f_K(x) - [x^i]2^{K+i+1} f_K(x)\).

Thus, \(\displaystyle [x^i]f_K(x) = \prod_{j=1}^{K} \frac{1-2^{i+j}}{1-2^j}\). Therefore, we can enumerate \([x^{N-K}]f_K(x)\) for \(1 \le K \le M\) in \(\mathrm{O}(N\log N)\) time. Below, let \(B_K\) be this count.

Next, let us find the expected value of the answer to Xor Optimization Problem for a sequence with such a basis as above.

By noticing that the \(X_i\)-th bit is always \(1\), we find that this value is \(\displaystyle \frac{(2^{X_M+1}-1) + (\sum_{i=1}^{K} 2^{X_i})}{2}\).

Finally, let us find the number of sequences of non-negative integers \(1 \le Y_1 < Y_2 < \dots < Y_K < 2^M\) such that the highest bit in \(Y_i\) is \(0\) in \(Y_j\) for each pair \(1 \le i < j \le K\) and the highest bit in \(Y_i\) is \(2^{X_i}\) for each \(1 \le i \le K\).

We have the following requirements for \(Y_i\): the highest bit of \(Y_i\) must be the \(X_i\)-th bit, and the \(X_j\)-th bits must be \(0\) for each \(1 \le j < i\). Thus, there are \(\displaystyle \prod_{i=1}^{K} 2^{X_i - (i-1)}\) such sequences.

Therefore, the problem asks us to find the sum, for all sequences of non-negative integers \(0 \le X_1 < X_2 < \dots < X_K < M\), of the values of the following:

・\(B_K \times \displaystyle \frac{(2^{X_K+1}-1) + (\sum_{i=1}^{K} 2^{X_i})}{2} \times \prod_{i=1}^{K} 2^{X_i - (i-1)}\).

First, let us handle the \(\sum_{i=1}^{K} 2^{X_i}\) part. After rearranging the product, we have \(B_K \times \sum_{i=1}^{K} 2^{X_i} \times 2^{\frac{K(K-1)}{2}} \times \prod_{i=1}^{K} 2^{X_i}\). Let us try to find the sum of \(\sum_{i=1}^{K} 2^{X_i} \times \prod_{i=1}^{K} 2^{X_i}\) for each \(K\).

Let \(C_K\) be the sum, for all size-\(K\) subsets of \(\{2^0,2^1,\dots,2^{M-1}\}\), of the products of the elements. Then, \(\sum_{i=1}^{K} 2^{X_i} \times \prod_{i=1}^{K} 2^{X_i}\) for a fixed \(K\) is \((2^M-1)C_K - (K+1)C_{K+1}\), which can be derived by seeing \(\sum_{i=1}^{K} 2^{X_i}\) as “\(2^M-1-\)(surplus).”

Next, let us handle the \(2^{X_K+1} - 1\) part. After rearranging the product, we have \(B_K \times (2^{X_K+1} - 1) \times 2^{\frac{K(K-1)}{2}} \times \prod_{i=1}^{K} 2^{X_i}\). The \(1\) part in \(2^{X_K+1} - 1\) can be easily represented using \(C_K\), so let us consider the \(2^{X_K}\) part below.

We want to find \(2^{X_K} \times \prod_{i=1}^{K} 2^{X_i}\) for a fixed \(K\), which can be done with divide-and-conquer in \(\mathrm{O}(M\log^2 M)\) time.

Therefore, we have solved the problem in \(\mathrm{O}(N\log N + M \log^2 M)\) time.