当前没有测试数据。

题目描述

给定正整数 $N$ 和 $K$。

请你求出所有满足以下条件的正整数 $x$ 的和，并对 $998244353$ 取模：

• $1 \le x \le N$；
• $\operatorname{popcount}(x) = K$。

共有 $T$ 组测试数据，你需要对每组数据分别求解。

什么是 popcount？

对于一个正整数 $y$，$\operatorname{popcount}(y)$ 表示它的二进制表示中 1 的个数。

例如：

• $\operatorname{popcount}(5)=2$，因为 $5$ 的二进制是 101；
• $\operatorname{popcount}(16)=1$，因为 $16$ 的二进制是 10000；
• $\operatorname{popcount}(25)=3$，因为 $25$ 的二进制是 11001。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行两个整数：

N K

表示一组测试数据。

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 组测试数据的答案，即所有满足条件的正整数之和对 $998244353$ 取模后的结果。

输入输出样例

样例输入

2
20 2
1234567890 17

样例输出

100
382730918

样例解释

对于第一组数据，所有不超过 $20$ 且 $\operatorname{popcount}(x)=2$ 的正整数共有 $9$ 个：

$3,5,6,9,10,12,17,18,20$

它们的和为：

$3+5+6+9+10+12+17+18+20 = 100$

由于 $100 \bmod 998244353 = 100$，所以第一行输出 100。

注意答案需要对 $998244353$ 取模。

数据范围

• $1 \le T \le 100$
• $1 \le N < 2^{60}$
• $1 \le K \le 60$

保证输入的 $T,N,K$ 均为整数。