← 返回题目列表

Codeforces · 1603/F

F. 2017 年 10 月 18 日

中文机器翻译题面 查看原题

那是2017年10月18日。Shohag,一个忧郁的灵魂,下定了一个坚定的决心,他将认真地、用心地追求竞争性编程,因为他发现它很有趣。一晃四年过去了,他很庆幸自己走上了这条路。他现在正在 Codeforces 上举办一场竞赛。他发现了一个令人震惊的问题,但不知道如何解决。帮助他解决本轮的最后一个问题。

给你三个整数 $$$n$$$、$$$k$$$ 和 $$$x$$$。求整数序列 $$$a_1, a_2, \ldots, a_n$$$ 的模 $$$998\,244\,353$$$ 的数量,满足以下条件:

- $$$0 \le a_i \lt 2^k$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$i$$$。
- $$$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 \lt 2^{\operatorname{min}(20, k)}$$$)。

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

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

6
2 2 0
2 1 1
3 2 3
69 69 69
2017 10 18
5 7 0

输出 #1

6
1
15
699496932
892852568
713939942

注意

在第一个测试用例中,有效序列为 $$$[1, 2]$$$、$$$[1, 3]$$$、$$$[2, 1]$$$、$$$[2, 3]$$$、$$$[3, 1]$$$ 和 $$$[3, 2]$$$。

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