CF1815D XOR Counting

记 $\bigoplus$ 表示按位异或运算。 给定整数 $n,m$。 记一个序列 $a$ 是好的，当且仅当它是一个长度为 $m$ 的非负整数序列，且其元素之和恰好为 $n$。 求在好的序列 $a$ 中，$\bigoplus_{i=1}^ma_i$ 的所有可能取值之和对 $998244353$ 取模后的值。 **对于一个 $\bm{\bigoplus_{i=1}^ma_i}$ 的可能取值，无论有多少个可以取得这个值的好的序列 $\bm{a}$，这个值都应只被计入所求之和一次。** 每个测试点包含 $t$ 组数据。

第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据： 输入一行两个整数 $n,m(0\leq n\leq10^{18};1\leq m\leq10^5)$。

对于每组数据： 输出一行一个整数表示 $\bigoplus_{i=1}^ma_i$ 的所有可能取值之和对 $998244353$ 取模后的值。 ### 样例解释 对于样例一： - 所有好的序列 $a$ 为 $[69]$，其所有元素按位异或和为 $69$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $69$，故答案为 $69$。 对于样例二： - 所有好的序列 $a$ 为 $[5,0],[4,1],[3,2],[2,3],[4,1],[0,5]$，其所有元素按位异或和分别为 $5,5,1,1,5,5$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $1,5$，故答案为 $1+5$，即 $6$。 对于样例三： - 所有好的序列 $a$ 为 $[0,0,0,0,0,0,0,0,0,0]$，其所有元素按位异或和为 $0$。 因此 $\bigoplus_{i=1}^ma_i$ 的所有可能取值为 $0$，故答案为 $0$。

For the first test case, we must have $ a_1=69 $ , so it's the only possible value of $ a_1 $ , therefore our answer is $ 69 $ . For the second test case, $ (a_1,a_2) $ can be $ (0,5), (1,4), (2,3), (3,2), (4,1) $ or $ (5,0) $ , in which $ a_1\bigoplus a_2 $ are $ 5,5,1,1,5,5 $ respectively. So $ a_1\bigoplus a_2 $ can be $ 1 $ or $ 5 $ , therefore our answer is $ 1+5=6 $ . For the third test case, $ a_1,a_2,\ldots,a_{10} $ must be all $ 0 $ , so $ a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0 $ . Therefore our answer is $ 0 $ .