33OJ
登录 注册

#P17732. [ICPC 2019 Xuzhou R] Cats line up

[ICPC 2019 Xuzhou R] Cats line up

题目描述

今天,你来到了一个猫村。这个村子里有 NN 只猫。每只猫都非常可爱,并且所有 NN 只猫都非常聪明,它们排成了一排。

这个村子里的猫非常特别!!!为什么这么说呢?因为这些猫的身高互不相同,且都是 11 到 NN 之间(包含两端)的整数。

众所周知,谁都不喜欢拍照时站在太高的人旁边,因为站在那样的人旁边会显得自己很矮。人是这样,猫也是如此。

每只猫都希望与它相邻的猫的身高差不超过 KK。如果一只猫与它的每个邻居的身高差都不超过 KK,它就会感到开心。

现在,给定这个村子里猫的数量以及猫所能接受的身高差 KK,你能计算出有多少种让所有猫都开心的排队方式吗?

输入格式

第一行包含一个整数 TT,表示你需要计算的 (N,K)(N, K) 的对数。 接下来的 TT 行,每行包含两个整数 NN 和 KK。

  • 1≤T≤1051 \le T \le 10^5
  • 1≤N≤1061 \le N \le 10^6
  • 1≤K≤31 \le K \le 3

输出格式

对于每组测试数据,输出一行一个整数 xx —— 使得所有猫都开心的排队方案数对 998244353998244353 取模的结果。

18
1 1
2 2
3 2
1 3
2 3
3 3
4 3
5 3
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 3
15 3
1
2
6
1
2
6
24
72
180
428
1042
2512
5912
13592
30872
69560
155568
345282

提示

翻译由 DeepSeek V4 Pro 完