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.