← 返回题目列表

Codeforces · 1868/C

C. 旅行计划

中文机器翻译题面 查看原题

中考结束后的暑假,汤姆和丹尼尔打算去旅行。

他们的国家/地区有 $$$n$$$ 个城市,编号从 $$$1$$$ 到 $$$n$$$。而且该国的交通系统非常特殊。对于每个城市 $$$i$$$ ($$$1 \le i \le n$$$),有

- 城市 $$$i$$$ 和 $$$2i$$$ 之间的道路,如果 $$$2i\le n$$$;
- 城市 $$$i$$$ 和 $$$2i+1$$$ 之间的道路,如果 $$$2i+1\le n$$$。

在制定旅行计划时,Daniel 为每个城市选择 $$$1$$$ 和 $$$m$$$ 之间的某个整数值,对于第 $$$i$$$ 个城市,我们用 $$$a_i$$$ 表示。

令$$$s_{i,j}$$$ 为城市$$$i$$$ 和$$$j$$$ 之间的简单$$$^\dagger$$$ 路径中城市的最大值。出行计划的得分为$$$\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$$$。

汤姆想知道所有可能的旅行计划的分数总和。丹尼尔请你帮他找到它。你只需要告诉他答案对 $$$998\,244\,353$$$ 取模即可。

$$$^\dagger$$$ 城市 $$$x$$$ 和 $$$y$$$ 之间的简单路径是它们之间最多经过每个城市一次的路径。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 200$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\leq n\leq 10^{18}$$$, $$$1\leq m\leq 10^5$$$) — 城市的数量和城市的最大值。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所有可能的旅行计划的分数总和,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5
3 1
2 2
10 9
43 20
154 147

输出 #1

6
19
583217643
68816635
714002110

注意

在第一个测试用例中,只有一个可能的旅行计划:

路径$$$1\rightarrow 1$$$:$$$s_{1,1}=a_1=1$$$。

路径$$$1\rightarrow 2$$$:$$$s_{1,2}=\max(1,1)=1$$$。

路径$$$1\rightarrow 3$$$:$$$s_{1,3}=\max(1,1)=1$$$。

路径$$$2\rightarrow 2$$$:$$$s_{2,2}=a_2=1$$$。

路径$$$2\rightarrow 1\rightarrow 3$$$:$$$s_{2,3}=\max(1,1,1)=1$$$。

路径$$$3\rightarrow 3$$$:$$$s_{3,3}=a_3=1$$$。

得分为$$$1+1+1+1+1+1=6$$$。

在第二个测试用例中,有四种可能的旅行计划:

计划$$$1$$$的分数:$$$1+1+1=3$$$。

计划$$$2$$$的分数:$$$1+2+2=5$$$。

计划$$$3$$$的分数:$$$2+2+1=5$$$。

计划$$$4$$$的分数:$$$2+2+2=6$$$。

因此,得分总和为$$$3+5+5+6=19$$$。