Subset Sum with a Recurrence Sequence

We are given a recurrence sequence \(\{a_n\}\) defined by \(a_n = \sum_{j=1}^{m} a_{n-j}\) for all \(n > m\) with the first \(m\) terms \(a_1, a_2, \dots, a_m\) provided as positive integers. For each query a positive integer \(x\) is given, and the task is to count the number of distinct subsets \(S\) (of positive integers representing indices) for which

[ \sum_{s\in S}a_s = x. ]

Since the answer can be very large, output it modulo \(998244353\). The input contains multiple test cases.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case is described as follows:

• The first line contains two integers \(m\) and \(q\): the number of initial terms and the number of queries.
• The second line contains \(m\) positive integers \(a_1, a_2, \dots, a_m\) which are the initial terms of the sequence.
• Then \(q\) lines follow, each containing one positive integer \(x\).

It is guaranteed that in each test case, only those terms \(a_n\) with \(a_n \le x_{\max}\) (where \(x_{\max}\) is the maximum query value of that test case) are considered when forming subsets.

outputFormat

For each query in every test case, print a single line containing the number of subsets \(S\) satisfying \(\sum_{s \in S}a_s=x\) modulo \(998244353\).

sample

3
2 3
1 2
1
3
5
3 2
1 1 2
4
5
4 3
1 3 2 1
1
7
8

1
2
2
2
2
2
1
2