You need to calculate $\sum\limits_{i=1}^n\sum\limits_{j=1}^n{\tbinom{i + j}{i} \cdot f(i + j, i)}$, where $f(0, x) = 0, f(1, x) = a,$ and for all $2 \leq m \leq x$, $f(m, x) = b \cdot f(m - 1, x) + c \cdot f(m - 2, x)$, and moreover, for all $m > x$, $f(m, x) = d \cdot f(m - 1, x) + e \cdot f(m - 2, x)$.
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $\tbinom {n}{k}$. It is the coefficient of the $x^k$ term in the polynomial expansion of the binomial power $(1 + x)^n$, and is given by the formula
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
Input
This problem contains multiple test cases.
The first line contains an integer $T(1 \leq T \leq 50)$ indicating the number of test cases.
The next $T$ lines each contains six integers $n, a, b, c, d, e(1 \leq n \leq 10 ^ 5, 1 \leq a, b, c, d, e \leq 10 ^ 6)$.
Output
Output $T$ lines, each line contains an integer indicating the answer.
Since the answer can be very large, you only need to output the answer modulo $998244353$.