October 18, 2017
Contest: Codeforces Round 752 (Div. 1)
Difficulty rating: 2700
Tags: combinatorics, dp, implementation, math

It was October 18, 2017. Shohag, a melancholic soul, made a strong determination that he will pursue Competitive Programming seriously, by heart, because he found it fascinating. Fast forward to 4 years, he is happy that he took this road. He is now creating a contest on Codeforces. He found an astounding problem but has no idea how to solve this. Help him to solve the final problem of the round.

You are given three integers $$$n$$$, $$$k$$$ and $$$x$$$. Find the number, modulo $$$998\,244\,353$$$, of integer sequences $$$a_1, a_2, \ldots, a_n$$$ such that the following conditions are satisfied:

- $$$0 \le a_i \lt 2^k$$$ for each integer $$$i$$$ from $$$1$$$ to $$$n$$$.
- There is no non-empty subsequence in $$$a$$$ such that the bitwise XOR of the elements of the subsequence is $$$x$$$.

A sequence $$$b$$$ is a subsequence of a sequence $$$c$$$ if $$$b$$$ can be obtained from $$$c$$$ by deletion of several (possibly, zero or all) elements.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$)  — the number of test cases.

The first and only line of each test case contains three space-separated integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le k \le 10^7$$$, $$$0 \le x \lt 2^{\operatorname{min}(20, k)}$$$).

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$5 \cdot 10^7$$$.

Output format:
For each test case, print a single integer — the answer to the problem.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the valid sequences are $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$ and $$$[3, 2]$$$.

In the second test case, the only valid sequence is $$$[0, 0]$$$.

Example input:
6
2 2 0
2 1 1
3 2 3
69 69 69
2017 10 18
5 7 0

Example output:
6
1
15
699496932
892852568
713939942

Editorial:
Idea: [user:YouKn0wWho], [user:Alpha_Q], [user:antontrygubO_o]
Thanks to Anton for writing editorial for this problem.
When $$$x = 0$$$, we need to count the number of sequences $$$(a_1, a_2, \ldots, a_n)$$$, such that the $$$a_i$$$s are linearly independent. Clearly, for $$$n>k$$$ there are no such sequences, and for $$$n \le k$$$, the answer is $$$(2^k-1)\cdot(2^k-2)\cdot \ldots \cdot (2^k - 2^{n-1})$$$, as $$$a_i$$$ can be any element not generated by the elements $$$a_1, a_2, \ldots, a_{i-1}$$$, and they generate exactly $$$2^{i-1}$$$ elements.
Now, let's deal with the case $$$x>0$$$. It's easy to see that the exact value of $$$x$$$ doesn't matter here, it's easy to construct a bijection between such sequences for this problem and such sequences for the case $$$x = 1$$$, by change of basis from the one which has $$$x$$$ as the first element to one which has $$$1$$$ as the first element. So from now on $$$x = 1$$$.
We will show that the answer for given $$$n, k$$$ is $$$$$$(2^k)^n \cdot 2^{k-1} - (2^{k-1})^n \cdot (2^{k-1}-1)\cdot 2^{k-2} + (2^{k-2})^n \cdot (2^{k-1}-1)(2^{k-2}-1)\cdot 2^{k-3} \ldots$$$$$$
More generally, it's
$$$$$$\sum_{i = 0}^{k}((-1)^i \cdot (2^{k-i})^n \cdot \prod_{j = 0}^{i-1} (2^{k-j-1}-1) 2^{k-i-1} )$$$$$$
This is easy to calculate in $$$O(k + \log{n})$$$, by calculating prefix products $$$P_i = \prod_{j = 0}^{i-1} (2^{k-j-1}-1)$$$ in $$$O(k)$$$, and finding $$$2^n$$$ in $$$O(\log{n})$$$ and its powers in $$$O(k)$$$. Now, let's prove the formula.
It's possible to prove the formula by some inclusion-exclusion arguments, but here we will present a bit more combinatorial approach. Let's just look at $$$(2^{k-i})^n \cdot \prod_{j = 0}^{i-1} (2^{k-j-1}-1) 2^{k-i-1}$$$ and find some combinatorial interpretation for it.
Let's consider a linear space of dimension $$$t$$$ (with $$$2^t$$$ elements), containing $$$1$$$. Consider all its subspaces of dimension $$$t-1$$$. Firstly, how many of them are there? Exactly $$$2^t-1$$$, each corresponding to the only nonzero element of the orthogonal complement of the subspace. It's easy to see that exactly $$$2^{t-1}-1$$$ of them will contain $$$1$$$, and other $$$2^{t-1}$$$ won't.
Then, there is a natural representation of the number $$$\prod_{j = 0}^{i-1} (2^{k-j-1}-1) 2^{k-i-1}$$$ — it's the number of sequences of spaces $$$(S_0, S_1, S_2, \ldots, S_{i-1}, S_i)$$$, where:
• $$$S_0$$$ is the whole space of our problem, of dimension $$$k$$$,
• For $$$j$$$ from $$$1$$$ to $$$i-1$$$, $$$S_j$$$ is a subspace of $$$S_{j-1}$$$ of dimension $$$k-j$$$, containing $$$1$$$.
• $$$S_i$$$ is a subspace of $$$S_{i-1}$$$ of dimension $$$k-i$$$, not containing $$$1$$$.
Then, $$$(2^{k-i})^n \cdot \prod_{j = 0}^{i-1} (2^{k-j-1}-1) 2^{k-i-1}$$$ is the number of sequences $$$(S_0, S_1, S_2, \ldots, S_{i-1}, S_i, a)$$$, where sets $$$S$$$ are described as above, and all elements of $$$a$$$ lie in $$$S_i$$$ (as there are $$$2^{k-i}$$$ ways to choose each of them).
This starts to resemble what we need... As in such structure, space generated by $$$a$$$ won't be able to contain $$$1$$$, and it's exactly the kind of arrays we are interested in.
So, we want to show that the actual number of arrays from the statement is equal to the number of tuples $$$(S_0, S_1, S_2, \ldots, S_{i-1}, S_i, a)$$$, where the tuple is counted with a plus sign for even $$$i$$$ and with a minus sign for odd $$$i$$$.
It's enough to prove that each array $$$a$$$ will be counted exactly once this way (meaning that it will be in tuples taken with plus one more time than in tuples taken with a minus). Fine, let's consider an array $$$a$$$ such that subspace spanned by it doesn't contain $$$1$$$ and look at the sequences of sets $$$(S_0, S_1, S_2, \ldots, S_{i-1}, S_i)$$$ such that $$$a$$$ is contained in $$$S_i$$$. If the subspace generated by $$$a$$$ is $$$T$$$, we just need all spaces to contain $$$T$$$. If size of $$$T$$$ is $$$t$$$, there is a bijection between such sequences and sequences $$$(S_0, S_1, S_2, \ldots, S_{i-1}, S_i)$$$, where
• $$$S_0$$$ is the space orthogonal to subspace $$$T$$$, of dimension $$$k-t$$$,
• For $$$j$$$ from $$$1$$$ to $$$i-1$$$, $$$S_j$$$ is a subspace of $$$S_{j-1}$$$ of dimension $$$k-t-j$$$, containing $$$1$$$.
• $$$S_i$$$ is a subspace of $$$S_{i-1}$$$ of dimension $$$k-t-i$$$, not containing $$$1$$$.
But the number of such sequences for a fixed $$$i$$$ is precisely $$$\prod_{j = 0}^{i-1} (2^{k-t-j-1}-1) \cdot 2^{k-t-i-1}$$$! So, we need to show that the sum of this (with correspondent signs) over $$$i$$$ from $$$0$$$ to $$$n-t$$$ is $$$1$$$. Let's replace $$$n-t$$$ by $$$n$$$, we need to show that $$$$$$\sum_{i = 0}^k ((-1)^i \cdot 2^{k-i-1} \cdot \prod_{j = 0}^{i-1}(2^{k-j-1}-1) ) = 1$$$$$$
This is easy to prove by induction, as after moving $$$2^{k-1}$$$ to the right side it's equivalent to $$$$$$\sum_{i = 1}^k ((-1)^i \cdot 2^{k-i-1} \cdot \prod_{j = 0}^{i-1}(2^{k-j-1}-1) ) = (1 - 2^{k-1})$$$$$$, and we can cancel $$$(1 - 2^{k-1})$$$ from both sides and get the same equation, but now for $$$k-1$$$.