CF1603F.October 18, 2017

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.

时间是2017年10月18日。肖哈格——一个忧郁的灵魂——下定决心，要全心全意地投身于算法竞赛编程，因为他发现这门学科令人着迷。时光飞逝，转眼已过四年，他为自己当初选择这条道路而感到欣慰。如今，他正在 Codeforces 上举办一场比赛。他发现了一道令人惊叹的题目，却毫无解题思路。请帮助他解决本轮比赛的最后一题。

给定三个整数 $n$、$k$ 和 $x$。求满足以下条件的整数序列 $a_1, a_2, \ldots, a_n$ 的个数（对 $998\,244\,353$ 取模）：

• 对每个 $i = 1, 2, \ldots, n$，均有 $0 \le a_i < 2^k$；
• 序列 $a$ 中不存在任何非空子序列，使得该子序列中所有元素的按位异或（XOR）结果等于 $x$。

若序列 $b$ 可通过从序列 $c$ 中删除若干（可能为零个或全部）元素得到，则称 $b$ 是 $c$ 的一个子序列。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^5$）—— 表示测试用例的数量。

每个测试用例仅有一行，包含三个以空格分隔的整数 $n$、$k$ 和 $x$（$1 \le n \le 10^9$，$0 \le k \le 10^7$，$0 \le x \lt 2^{\operatorname{min}(20, k)}$）。

保证所有测试用例中 $k$ 的总和不超过 $5 \cdot 10^7$。

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

对于每个测试用例，输出一个整数——即该问题的答案。

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]$.

在第一个测试用例中，合法的序列有 $[1, 2]$、$[1, 3]$、$[2, 1]$、$[2, 3]$、$[3, 1]$ 和 $[3, 2]$。

在第二个测试用例中，唯一合法的序列是 $[0, 0]$。