8550: Find the Number of Paths

Huah has $n+k$ cities numbered 1,2,.... ,n+k the city $(1\le i<n+k)$ to the city i+1 has n+k-idistinct one-way roads.

For each x=1,2,...,n-1,the city $(x<i\le n+k)$ to the city $i-x$ has ax distinct one-way roads.

For m=k+1,k+2,... ,k+n,find the number of paths from city k+1 to city $m$ that pass through exactly k number of roads.

Two paths are distinct when and only if the sequence of edges they pass through is distinct and the answer is modulo 998244353

First line has one integer $(1\le T\le 14)$, indicating there are T test cases. In each case:

First line input two integers n,k(2≤n≤2×105,1≤k≤2×105).

Second line n-1 integers a1,a2,...,an−1(0≤ai≤998244352).

There is a blank line between case$i(1\le i<T)$ and case $i+1$.

Input guarantee $\sum (n+k)\le 1006769$.

4
3 2
1 2

3 1
1 2

5 10
2 3 3 3

3 3
166374059 748683265

5 0 2
0 2 0
114307026 825469567 425461680 73846080 5140800
5 2 0