P8565 Sultan Rage

There is a sequence $\{a_n\}$ such that for all $n > m$, $a_n=\sum\limits_{j=1}^m a_{n-j}$. Also, $a_1,a_2,\cdots,a_m$ are positive integers given in the input. There are $q$ queries. Each query gives a positive integer $x$, and asks how many distinct positive-integer sets $S$ (no repeated elements) satisfy $\sum\limits_{s\in S}a_s=x$. The answer is taken modulo the prime $998244353$. This problem contains multiple test cases.

**This problem contains multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains two integers $m,q$. The second line contains $m$ integers $a_1,a_2,\cdots,a_m$. The third line contains $q$ integers, where each integer represents one query.

For each query, output one line containing the answer.

For all testdata, $T=5$, $2 \le m \le 100$, $1 \le q,a_i \le 100$, $1 \le x \le 10^{18}$. $$ \def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c}\hline \textbf{测试点编号}&\bm{m\le}&\bm{q \le }&\bm{a_i \le }& \bm{x \le}&\bm{\textbf{特殊性质}}\cr\hline \textsf1\sim \sf2 & 8&8 & 8 & 100\cr\hline \sf3\sim 5 & 15& &15&10^3 \cr\hline \textsf6 & & & & 1 &\cr\hline \sf7\sim 11 & & 1& & & \textsf{A}\cr\hline \sf12\sim 16 & 2& & &\cr\hline \sf17\sim 20 & &\cr\hline \end{array} $$ $\textsf A$: $m=10$, and $x$ is generated uniformly at random among all possible $x$. Translated by ChatGPT 5