Given a function f(x)=bc+eax+df(x)=bc+eax+d, where a≢0(mod998244353)a≢0(mod998244353).
Denote x0x0 as the smallest real solution of the equation: ax+d=0ax+d=0, and note that the solution always exists.
Output the coefficient of the item (x−x0)n(x−x0)n in the Taylor series of f(x)f(x) at x=x0x=x0. The answer may be very large, so you just need to output the answer modulo 998244353998244353.
Note that for the given nn, your task is to answer qq queries which share the same parameter nn.
Note that it is not guaranteed that the answer could be represented as rational fraction pqpqwhere gcd(p,q)=1gcd(p,q)=1, or qq has no multiplicative inverse element modulo 998244353998244353. If it can, print it as pq−1pq−1 modulo 998244353998244353 which is not negative. Otherwise just print −1−1.
If you knew little about gcdgcd in mathematic, please refer tohttps://en.wikipedia.org/wiki/Greatest_common_divisor
If you knew little about Taylor_seriesTaylor_series in mathematic, please refer tohttps://en.wikipedia.org/wiki/Taylor_series
Input
There are multiple test cases.
Each case starts with a line containing two integers nn and qq seperated by a space.
Next qq lines in every test case will include four integers aa, bb, cc, dd per line, seperated by 33spaces.
It is guaranteed that ∀t∈{a,b,c,d},|t|≤109∀t∈{a,b,c,d},|t|≤109 and n,q∈[0,5×104]n,q∈[0,5×104].
It is guaranteed that the sum of nn and the sum of qq in all test cases are both no larger than 3×1053×105.
Output
For each query in each test case, output the only line containing just one integer denoting the answer if there would be, or −1−1 otherwise.