← 返回题目列表

AtCoder · arc209_e

E. 我讨厌ABC

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

分数: 1100 点

问题陈述

求模数 998244353,字符串 S 长度 N 组成 A, B, C 使得以下值等于 K:

  • 的(不一定是连续的)子序列的最大长度 S 不包含 ABC 作为(不一定是连续的)子序列

你被给予 T 测试用例。解决它们中的每一个。

约束

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 10^6
  • \max(0,N-100) \le K \le N

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个案例均按以下格式给出:

N\ K

输出

输出 T 行。的 i第行 (1 \le i \le T) 应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

4
4 3
8 6
123 100
123456 123400

示例输出 1

9
462
741573397
255048895

对于第一个测试用例,例如, ACBC 满足条件。 ACBC 本身包含 ABC 作为子序列,并且 ACC 不包含 ABC 作为子序列,因此不包含的子序列的最大长度 ABC 作为子序列是 3。 满足条件的其他示例包括 AABC 和 ABCA.