Several days ago, ZCC found a summation formula on Miss G.'s scratch pad:
$$ \sum_{i\geq 0} \sum_{j\geq 0} (-1)^{s+t+i+j} {{s} \choose {i}} {{t} \choose {j}} {{n+pi+qj} \choose {m}} $$
$n, m, p, q, s, t$ are positive integers given which satisfy:
$ s,t\leq 10^9 $
$ s+t\leq m\leq s+t+50$
$ p,q \leq 20000 $
$ m\leq n \leq 10^{18} $
Please help him compute the result, modulo 998244353.
First line contains a single integer $T(T=100)$ which denotes the number of test cases.
For each test case, there are four integers in a row: $n, m, p, q, s, t$.
For 80% of the test cases, $p, q \leq 1000$.
For each test case, output a single line which is the answer.