← 返回题目列表

AtCoder · abc381_g

G. 斐波那契积

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

分数: 675 点

问题陈述

定义一个序列 a_1, a_2, a_3, \dots 如下:

a_n = \begin{cases} x & (n=1) \\ y & (n=2) \\ a_{n-1} + a_{n-2} & (n \geq 3) \\ \end{cases}

查找 每对 \left( \displaystyle \prod_{i=1}^N a_i \right) \bmod{998244353}.

你被给予 T 测试用例解决。

约束

  • 1 \leq T \leq 5
  • 1 \leq N \leq 10^{18}
  • 0 \leq x \leq 998244352
  • 0 \leq y \leq 998244352
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出。在这里, \mathrm{case}_i 表示 i- 第一个测试用例。 总共

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

每个测试用例均按以下格式给出:

N x y

输出

打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。 总共


示例输入 1

3
5 1 1
2024 11 22
1000000000000000000 12345 6789

示例输出 1

30
577322229
726998219

对于第一个测试用例,序列的元素是 1, 1, 2, 3, 5, 8, \dots。因此,答案是 (1 \times 1 \times 2 \times 3 \times 5) \bmod{998244353} = 30.