G. Da7doo7
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$Da7doo7$$$ believed he had mastered competitive programming contests, so he decided to turn his attention to playing basketball.

$$$Da7doo7$$$ intends to shoot $$$n$$$ balls into the basket. The probability of him scoring the first shot is $$$\frac{p_0}{q_0}$$$.

For subsequent shots, his probability of scoring depends on whether he made the previous shot or not:

If he scored shot $$$i-1$$$, the probability of scoring shot $$$i$$$ is $$$\frac{p_1}{q_1}$$$.

If he missed shot $$$i-1$$$, the probability of scoring shot $$$i$$$ is $$$\frac{p_2}{q_2}$$$.

$$$Da7doo7$$$ is asking for your help to find the expected value of the number of balls that will score.

We can show that the answer can be written in the form $$$\frac{P}{Q}$$$ where $$$P, Q$$$ are coprime integers and $$$Q \neq 0 \bmod 998244353$$$. Output the value of $$$(P \cdot Q^{-1})$$$ modulo $$$998244353$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 5 \times 10^4$$$) — the number of testcases.

The first line of each testcase contains an integer $$$n$$$ ($$$1 \le n \le 10^{12}$$$) — the number of balls he will shoot.

The second line of each testcase contains six integers $$$p_0,q_0,p_1,q_1,p_2,q_2$$$ ($$$0 \le p_0,p_1,p_2 \le 10^{3}$$$ , $$$1 \le q_0,q_1,q_2 \le 10^{3}$$$).

Output

An integer representing the expected value of the number of balls that will score, modulo $$$998244353$$$.

Example
Input
5
2
5 10 2 10 3 10
10
7 10 5 10 2 10
5
1 5 7 10 9 10
100
1 1 1 10 1 1
100000000
75 100 55 100 23 100
Output
249561089
965715715
403450441
210477862
330198862