您已收到生日礼物 — $$$n$$$ 整数的三倍!其中第 $$$i$$$ 是 $$$\lbrace a_{i}, b_{i}, c_{i} \rbrace$$$。所有数字都大于或等于 $$$0$$$,并且严格小于 $$$2^{k}$$$,其中 $$$k$$$ 是固定整数。
有一天,你玩三元组感到很累。于是你想出了三个新整数$$$x$$$、$$$y$$$、$$$z$$$,然后组成了$$$n$$$数组。第 $$$i$$$ 数组由重复 $$$x$$$ 次的 $$$a_i$$$ 、重复 $$$y$$$ 次的 $$$b_i$$$ 和重复 $$$z$$$ 次的 $$$c_i$$$ 组成。因此,每个数组的长度为$$$(x + y + z)$$$。
您希望从每个数组中精确选择一个整数,使得它们的 XOR(按位异或)等于 $$$t$$$。输出为 $$$0$$$ 和 $$$2^{k} - 1$$$(含)之间的每个 $$$t$$$ 选择数字的方法数,以 $$$998244353$$$ 为模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{5}$$$, $$$1 \leq k \leq 17$$$) — 数组的数量和所有数字的二进制长度。
第二行包含三个整数 $$$x$$$、$$$y$$$、$$$z$$$ ($$$0 \leq x,y,z \leq 10^{9}$$$) — 您选择的整数。
然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含三个整数 $$$a_{i}$$$、$$$b_{i}$$$ 和 $$$c_{i}$$$ ($$$0 \leq a_{i} , b_{i} , c_{i} \leq 2^{k} - 1$$$) - 构成第 $$$i$$$ 数组的整数。
输出
打印包含 $$$2^{k}$$$ 整数的单行。其中第 $$$i$$$ 应该是从每个数组中精确选择一个整数的方法数,以便它们的 XOR 等于 $$$t = i-1$$$ 模 $$$998244353$$$。
示例
输入 #1
1 1 1 2 3 1 0 1
输出 #1
2 4
输入 #2
2 2 1 2 1 0 1 2 1 2 3
输出 #2
4 2 4 6
输入 #3
4 3 1 2 3 1 3 7 0 2 5 1 0 6 3 3 2
输出 #3
198 198 126 126 126 126 198 198
注意
在第一个例子中,我们形成的数组是$$$(1, 0, 0, 1, 1, 1)$$$,我们有两种选择来得到$$$0$$$作为XOR,四种选择来得到$$$1$$$。
在第二个示例中,两个数组是 $$$(0, 1, 1, 2)$$$ 和 $$$(1, 2, 2, 3)$$$。总共有十六个$$$(4 \cdot 4)$$$选项,其中$$$4$$$($$$1 \oplus 1$$$和$$$2 \oplus 2$$$,每个选项两个)给出$$$0$$$,$$$2$$$其中($$$0 \oplus 1$$$和$$$2 \oplus 3$$$)给出$$$1$$$,其中 $$$4$$$($$$0 \oplus 2$$$ 和 $$$1 \oplus 3$$$,各两个选项)给出 $$$2$$$,最后 $$$6$$$ 其中($$$0 \oplus 3$$$、$$$2 \oplus 1$$$ 和 $$$1 \oplus 2$$$ 的四个选项)给出 $$$3$$$。