ZCC loves math

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.

3
3 2 1 1 1 1 
5 3 1 1 1 1 
10 7 2 3 2 3

1
5
9963

BestCoder Round #41