AT_abc406_e [ABC406E] Popcount Sum 3

[problemUrl]: https://atcoder.jp/contests/abc406/tasks/abc406_e 给定正整数 $N, K$。 请求出所有小于等于 $N$ 的正整数 $x$ 中，满足以下条件的数的**总和**，并将结果对 $998244353$ 取模。 - $x$ 的 $\mathrm{popcount}$ 值恰好为 $K$。 给定 $T$ 个测试用例，请分别求出答案。 $\mathrm{popcount}$ 指的是，对于正整数 $y$，其 $\mathrm{popcount}$ 值 $\mathrm{popcount}(y)$ 表示 $y$ 在二进制表示中数字 $1$ 出现的次数。例如，$\mathrm{popcount}(5)=2$，$\mathrm{popcount}(16)=1$，$\mathrm{popcount}(25)=3$。

输入按以下格式从标准输入给出。 > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ $\mathrm{case}_i$ 表示第 $i$ 个测试用例。每个测试用例按以下格式给出。 > $N$ $K$

输出 $T$ 行。第 $i$ 行 $(1 \leq i \leq T)$ 输出第 $i$ 个测试用例的答案。

**「数据范围」** - $1 \leq T \leq 100$ - $1 \leq N < 2^{60}$ - $1 \leq K \leq 60$ - $T, N, K$ 均为整数 **「样例 1 解释」** 对于第 $1$ 个测试用例，小于等于 $20$ 的正整数中，$\mathrm{popcount}$ 值为 $2$ 的数有 $3, 5, 6, 9, 10, 12, 17, 18, 20$，共 $9$ 个，它们的总和是 $100$。 $100$ 对 $998244353$ 取模的结果是 $100$，因此第 $1$ 行输出 $100$。 请注意需要输出对 $998244353$ 取模的余数。