给定两个正整数 $$$n$$$ 和 $$$m$$$。求 $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ 的所有可能值的总和,其中 $$$a_1,a_2,\ldots,a_m$$$ 是非负整数,使得 $$$a_1+a_2+\ldots+a_m=n$$$。
请注意,所有可能的值 $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ 应在总和中只计算一次。
由于答案可能太大,请输出对 $$$998244353$$$ 取模的答案。
这里,$$$\bigoplus$$$ 表示按位异或运算。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$0\le n\le 10^{18}, 1\le m\le 10^5$$$) — 分别是集合中整数的总和和数量。
输出
对于每个测试用例,输出所有非负整数 $$$a_1,a_2,\ldots,a_m$$$ 中 $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ 的所有可能值的总和,其中 $$$a_1+a_2+\ldots+a_m=n$$$。由于答案可能太大,请输出对 $$$998244353$$$ 取模的答案。
示例
输入 #1
7 69 1 5 2 0 10 420 69 12 26 73 34 1000000000000000000 10
输出 #1
69 6 0 44310 42 1369 216734648
注意
对于第一个测试用例,我们必须有 $$$a_1=69$$$,因此它是 $$$a_1$$$ 唯一可能的值,因此我们的答案是 $$$69$$$。
对于第二个测试用例,$$$(a_1,a_2)$$$ 可以是 $$$(0,5), (1,4), (2,3), (3,2), (4,1)$$$ 或 $$$(5,0)$$$,其中 $$$a_1\bigoplus a_2$$$ 是分别为$$$5,5,1,1,5,5$$$。所以 $$$a_1\bigoplus a_2$$$ 可以是 $$$1$$$ 或 $$$5$$$,因此我们的答案是 $$$1+5=6$$$。
对于第三个测试用例,$$$a_1,a_2,\ldots,a_{10}$$$ 必须全部为 $$$0$$$,因此 $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$$$。因此我们的答案是$$$0$$$。