103816: [Atcoder]ABC381 G - Fibonacci Product

Problem Statement

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

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$.

问题陈述

定义一个数列 $a_1, a_2, a_3, \dots$ 如下：

求 $\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$。