这是问题的困难版本。简单版本和困难版本之间的唯一区别是 $$$m$$$ 的约束。只有两个版本都解决了,你才能进行黑客攻击。
Chiori 喜欢娃娃,现在她要装饰她的卧室!
作为一个娃娃收藏家,Chiori 拥有 $$$n$$$ 娃娃。第 $$$i$$$ 个娃娃具有非负整数值 $$$a_i$$$($$$a_i < 2^m$$$,给出 $$$m$$$)。 Chiori想要挑选一些(也许是零个)娃娃来装饰,所以有$$$2^n$$$不同的挑选方式。
令 $$$x$$$ 为 Chiori 选择的玩偶值的按位异或和(如果 Chiori 没有选择玩偶 $$$x = 0$$$)。该拾取方式的值等于$$$x$$$的二进制表示中的$$$1$$$位的数量。更正式地说,它也等于索引的数量 $$$0 \leq i < m$$$,因此 $$$\left\lfloor \frac{x}{2^i} \right\rfloor$$$ 是奇数。
告诉她从 $$$0$$$ 到 $$$m$$$ 的每个整数 $$$i$$$ 的值为 $$$i$$$ 的挑选方式的数量。由于答案可能非常庞大,请按模 $$$998\,244\,353$$$ 打印它们。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 53$$$) — 娃娃的数量和拾取方式的最大值。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^m$$$) — 娃娃的值。
输出
打印 $$$m+1$$$ 整数 $$$p_0, p_1, \ldots, p_m$$$ — $$$p_i$$$ 等于值为 $$$i$$$ 的拾取路数除以 $$$998\,244\,353$$$ 模。
示例
输入 #1
4 4 3 5 8 14
输出 #1
2 2 6 6 0
输入 #2
6 7 11 45 14 9 19 81
输出 #2
1 2 11 20 15 10 5 0