G - Fibonacci Product Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

数列 a_1, a_2, a_3, \dots の一般項 a_n を次のように定義します。

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, 1, 2, 3, 5, 8, \dots です。よって (1 \times 1 \times 2 \times 3 \times 5) \bmod{998244353} = 30 が答えとなります。

Score : 675 points

Problem Statement

Define a sequence a_1, a_2, a_3, \dots as follows:

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

Find \left( \displaystyle \prod_{i=1}^N a_i \right) \bmod{998244353}.

You are given T test cases to solve.

Constraints

  • 1 \leq T \leq 5
  • 1 \leq N \leq 10^{18}
  • 0 \leq x \leq 998244352
  • 0 \leq y \leq 998244352
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.

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

Each test case is given in the following format:

N x y

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

3
5 1 1
2024 11 22
1000000000000000000 12345 6789

Sample Output 1

30
577322229
726998219

For the first test case, the elements of the sequence are 1, 1, 2, 3, 5, 8, \dots. Thus, the answer is (1 \times 1 \times 2 \times 3 \times 5) \bmod{998244353} = 30.