异或计数

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定非负整数 $n$ 和正整数 $m$。考虑所有长度为 $m$、元素均为非负整数且元素和恰好为 $n$ 的序列。

对每个序列计算所有元素的按位异或和。一个异或值无论能由多少个序列得到，都只计入一次。

求所有可能异或值之和对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $t$，表示数据组数。

接下来 $t$ 行，每行包含两个整数 $n,m$。

输出格式

对每组数据输出一行一个整数，表示答案。

样例输入 1

7
69 1
5 2
0 10
420 69
12 26
73 34
1000000000000000000 10

样例输出 1

69
6
0
44310
42
1369
216734648

数据范围

$1\le t\le 10^4$，$0\le n\le 10^{18}$，$1\le m\le 10^5$。