CF1603F October 18, 2017

2017 年 10 月 18 日，Shohag 是一个多愁善感的人，他下定决心要认真地投入到竞赛编程中，因为他觉得这很有趣。四年后，他很庆幸自己选择了这条路。现在他正在 Codeforces 上出题。他发现了一个令人惊叹的问题，但却不知道如何解决。请你帮助他解决本轮的最后一道题。 给定三个整数 $n$、$k$ 和 $x$。请你计算满足以下条件的整数序列 $a_1, a_2, \ldots, a_n$ 的数量，答案对 $998\,244\,353$ 取模： - 对于每个 $i$（$1 \le i \le n$），都有 $0 \le a_i < 2^k$。 - 序列 $a$ 中不存在非空子序列，其所有元素的按位异或值等于 $x$。 如果序列 $b$ 可以通过从序列 $c$ 中删除若干（可以为零或全部）元素得到，则称 $b$ 是 $c$ 的一个子序列。

第一行包含一个整数 $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 < 2^{\min(20, k)}$）。 保证所有测试用例中 $k$ 的总和不超过 $5 \cdot 10^7$。

对于每个测试用例，输出一个整数，表示满足条件的序列数量。

在第一个测试用例中，合法的序列有 $[1, 2]$、$[1, 3]$、$[2, 1]$、$[2, 3]$、$[3, 1]$ 和 $[3, 2]$。 在第二个测试用例中，唯一合法的序列是 $[0, 0]$。 由 ChatGPT 4.1 翻译