Given a function $f(x) = \frac{b}{c + e^{ax+d}}$, where $a \not \equiv 0 \pmod{998244353}$.

Denote $x_0$ as the smallest real solution of the equation: $ax+d=0$, and note that the solution always exists.

Output the coefficient of the item $(x-x_0)^n$ in the Taylor series of $f(x)$ at $x=x_0$. The answer may be very large, so you just need to output the answer modulo $998244353$.

Note that for the given $n$, your task is to answer $q$ queries which share the same parameter $n$.

Note that it is not guaranteed that the answer could be represented as rational fraction $\frac{p}{q}$ where $gcd(p,q)=1$, or $q$ has no multiplicative inverse element modulo $998244353$. If it can, print it as $pq^{-1}$ modulo $998244353$ which is not negative. Otherwise just print $-1$.

If you knew little about $gcd$ in mathematic, please refer to https://en.wikipedia.org/wiki/Greatest_common_divisor

If you knew little about $Taylor\_series$ in mathematic, please refer to https://en.wikipedia.org/wiki/Taylor_series

There are multiple test cases.

Each case starts with a line containing two integers $n$ and $q$ seperated by a space.

Next $q$ lines in every test case will include four integers $a$, $b$, $c$, $d$ per line, seperated by $3$ spaces.

It is guaranteed that $\forall t \in \{a,b,c,d\},|t| \le 10^9$ and $n,q \in [0,5 \times 10^4]$.

It is guaranteed that the sum of $n$ and the sum of $q$ in all test cases are both no larger than $3 \times 10^5$.

For each query in each test case, output the only line containing just one integer denoting the answer if there would be, or $-1$ otherwise.